树链剖分代码求助
本帖最后由 柿子饼同学 于 2023-9-28 10:37 编辑题目: P4315
不要用 GPT 回复....
求助求助 , 样例过了但是 0 分 , 必有鱼币重谢{:10_266:}
多谢了...
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, u, v, w, k;
vector<int> e, d, id;
// e 是树, d 是每条边的边权, id 是每条边的编号
// 因为不会链式前向星...
map<int, int> dict;
// dict 返回一个编号的边对应的节点编号
int data;
// 每个边的值, 为了方便都会转移到这条边上深度较大的点上
int size, hc, pa, dep;
// hc 是重孩子
int dfn, rdfn, top, tot;
string op;
void dfs1(int u, int par){
size = 1;
pa = par;
dep = dep + 1;
for(int i = 0; i < e.size(); i++){
if(e == par) continue;
data] = d;
dict] = e;
dfs1(e, u);
size += size];
if(size] > size]) hc = e;
}
}
void dfs2(int u, int t){
top = t;
dfn = ++tot;
rdfn = u;
if(!hc) return ;
dfs2(hc, t);
for(auto ed : e){
if(ed == pa || ed == hc) continue;
dfs2(ed, ed);
}
}
struct Segment_Tree{
#define lc u<<1
#define rc u<<1|1
struct Node{
int l, r, tr, add, maxv;
} t;
void pushup(int u){
t.maxv = max(t.maxv, t.maxv);
}
void pushdown(int u){
if(t.tr){
t.tr = t.tr = t.tr;
t.maxv = t.maxv = t.tr;
t.add = t.add = 0;
t.tr = 0;
}
if(t.add){
t.maxv += t.add;
t.add += t.add;
t.maxv += t.add;
t.add += t.add;
t.add = 0;
}
}
void build(int u, int l, int r){
t = {l, r};
if(l == r){
t.maxv = data];
t.add = t.tr = 0;
return ;
}
auto mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(u);
}
void trans(int u, int l, int r, int val){ // 全部改
if(l <= t.l && t.r <= r){
t.tr = val;
t.maxv = val;
return ;
}
auto mid = (t.l + t.r) >> 1;
pushdown(u);
if(l <= mid) trans(lc, l, r, val);
if(r > mid) trans(rc, l, r, val);
pushup(u);
}
void modify(int u, int l, int r, int val){ // 区间加
if(l <= t.l && t.r <= r){
t.add += val;
t.maxv += val;
return ;
}
auto mid = (t.l + t.r) >> 1;
pushdown(u);
if(l <= mid) modify(lc, l, r, val);
if(r > mid) modify(rc, l, r, val);
pushup(u);
}
int query(int u, int l, int r){
if(l <= t.l && t.r <= r){
return t.maxv;
}
auto mid = (t.l + t.r) >> 1;
int res = 0;
pushdown(u);
if(l <= mid) res = max(res, query(lc, l, r));
if(r > mid) res = max(res, query(rc, l, r));
return res;
}
} sgt;
int Max(int u, int v){
int res = 0;
while(top != top){
if(dep] < dep]) swap(u, v);
res = max(res, sgt.query(1, dfn], dfn));
u = pa];
}
res = max(res, sgt.query(1, min(dfn, dfn), max(dfn, dfn)));
return res;
}
void Change(int k, int w){
sgt.trans(1, dfn, dfn, w);
}
void Cover(int u, int v, int w){
while(top != top){
if(dep] < dep]) swap(u, v);
sgt.trans(1, dfn], dfn, w);
u = pa];
}
sgt.trans(1, min(dfn, dfn), max(dfn, dfn), w);
}
void Add(int u, int v, int w){
while(top != top){
if(dep] < dep]) swap(u, v);
sgt.modify(1, dfn], dfn, w);
u = pa];
}
sgt.modify(1, min(dfn, dfn), max(dfn, dfn), w);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i < n; i++){
cin >> u >> v >> w;
e.emplace_back(v);
e.emplace_back(u);
d.emplace_back(w);
d.emplace_back(w);
id.emplace_back(i);
id.emplace_back(i);
}
dfs1(1, 0);
dfs2(1, 1);
sgt.build(1, 1, n);
while(cin >> op){
if(op == 'S') break;
if(op == 'C'){
if(op == 'h'){
cin >> k >> w;
Change(dict, w);
}
else{
cin >> u >> v >> w;
Cover(u, v, w);
}
}
else if(op == 'A'){
cin >> u >> v >> w;
Add(u, v, w);
}
else{
cin >> u >> v;
cout << Max(u, v) << '\n';
}
}
return 0;
}
这是一段树链剖分的代码，用于解决树上路径问题。具体来说，它可以支持以下操作：
1. 修改某个边的权值
2. 将某个路径上的所有边的权值都改为同一个值
3. 将某个路径上的所有边的权值都加上同一个值
4. 查询某个路径上的最大权值
在这段代码中，树的节点编号从1开始，边的编号从1开始。节点的子节点存储在vector<int> e中，每条边的权值存储在vector<int> d中，每条边的编号存储在vector<int> id中。通过dfs1函数可以预处理出每个节点的重孩子和每个节点的深度。通过dfs2函数可以预处理出每个节点所在重链的顶端节点、每个节点的dfs序和反向dfs序。通过Segment_Tree结构体可以维护每个节点所在重链的区间最大值和区间加操作。
具体操作实现如下：
1. 修改某个边的权值：通过dict映射得到这条边的两个端点，然后调用sgt.trans函数将这个端点对应的节点的权值改为w。
2. 将某个路径上的所有边的权值都改为同一个值：从u节点开始，沿着重链向上走，每次调用sgt.trans函数将当前节点到它所在重链顶端节点这条路径上的所有节点的权值都改为w。
3. 将某个路径上的所有边的权值都加上同一个值：与操作2类似，只是调用的是sgt.modify函数。
4. 查询某个路径上的最大权值：从u节点开始，沿着重链向上走，每次调用sgt.query函数查询当前节点到它所在重链顶端节点这条路径上的最大权值。最后将所有查询到的最大权值取一个最大值即可。
希望这些解释能够帮助你理解这段代码。 代码中存在一些问题，导致你的程序得不到正确的结果。以下是我发现的一些问题和相应的修改建议：
1. 在 dfs1 函数中，初始化 hc 时应为 hc = 0; 而不是 hc = e;。因为可能存在没有孩子节点的情况。
2. 在 dfs2 函数中，递归调用 dfs2(ed, ed); 应改为 dfs2(ed, t);。因为轻边的重链顶端节点应与当前节点保持一致。
3. 在 Segment_Tree 结构体中，成员变量 add 和 tr 的初始值应设为 0，而不是未定义的随机值。
4. 在 trans 函数中，更新左右子节点时应先推送下去再更新，即将 pushdown(u) 放在两个递归之前。
5. 在 modify 函数中，同样需要将 pushdown(u) 放在两个递归之前。
6. 在 query 函数中，同样需要将 pushdown(u) 放在两个递归之前。
7. 在 Max 函数中，获取查询范围时，应使用 max(dfn, dfn) + 1，即将 max(dfn, dfn) 的值加 1。
请按照上述修改建议进行代码修改，然后重新运行程序，看看是否能够得到正确的结果。
球一个最佳答案谢谢啦！这对我非常重要！{:10_254:}{:10_254:}{:10_254:}
页:
[1]