样例过了但是全WA。自己对拍了一组,发现问题大概是点权转边权时修改操作的错误,但是不知道怎么调。
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
int n,m,root,MOD;
int w[N],siz[N],dfn[N],son[N];
int top[N],fa[N],dep[N],cnt;
int idx,h[N],ne[N],e[N],a[N],u[N],v[N];
struct{
int max,Lazt,res = 0;
}tree[N<<2];
void add(int x,int y){
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
inline int ls(int x){return x<<1;}
inline int rs(int x){return (x<<1)|1;}
inline void Push_up(int p){
tree[p].max = max(tree[ls(p)].max,tree[rs(p)].max);
}
void res_down(int s,int t,int p){
if(tree[p].res != 0){
tree[ls(p)].max = tree[p].res;
tree[rs(p)].max = tree[p].res;
tree[ls(p)].res = tree[p].res;
tree[rs(p)].res = tree[p].res;
tree[ls(p)].Lazt = 0;
tree[rs(p)].Lazt = 0;
tree[p].res = 0;
}
}
void Lazt_down(int s,int t,int p){
if(tree[p].Lazt){
tree[ls(p)].max += tree[p].Lazt;
tree[rs(p)].max += tree[p].Lazt;
tree[ls(p)].Lazt += tree[p].Lazt;
tree[rs(p)].Lazt += tree[p].Lazt;
tree[p].Lazt = 0;
}
}
void Push_down(int s,int t,int p){
res_down(s,t,p);
Lazt_down(s,t,p);
}
void Build(int s,int t,int p){
if(s == t){
tree[p].max = a[s];
tree[p].Lazt = 0;
tree[p].res = 0;
return;
}
int mid = s+((t-s)>>1);
Build(s,mid,ls(p));
Build(mid+1,t,rs(p));
Push_up(p);
}
void Update1(int l,int r,int k,int s,int t,int p){
if(l <= s && t <= r){
tree[p].max = k;
tree[p].res = k;
tree[p].Lazt = 0;
return;
}
Push_down(s,t,p);
int mid = s+((t-s)>>1);
if(l <= mid) Update1(l,r,k,s,mid,ls(p));
if(r > mid) Update1(l,r,k,mid+1,t,rs(p));
Push_up(p);
}
void Update2(int l,int r,int k,int s,int t,int p){
if(l <= s && t <= r){
res_down(s,t,p);
tree[p].max += k;
tree[p].Lazt += k;
return;
}
Push_down(s,t,p);
int mid = s+((t-s)>>1);
if(l <= mid) Update2(l,r,k,s,mid,ls(p));
if(r > mid) Update2(l,r,k,mid+1,t,rs(p));
Push_up(p);
}
int Getsum(int l,int r,int s,int t,int p){
if(l <= s && t <= r) return tree[p].max;
Push_down(s,t,p);
int mid = s+((t-s)>>1),ans = 0;
if(l <= mid) ans = max(ans,Getsum(l,r,s,mid,ls(p)));
if(r > mid) ans = max(ans,Getsum(l,r,mid+1,t,rs(p)));
return ans;
}
void dfs1(int u,int father){
fa[u] = father; siz[u] = 1;
dep[u] = dep[father]+1;
for(int i = h[u];i != -1;i = ne[i]){
if(e[i] == father) continue;
int v = e[i]; dfs1(v,u);
siz[u] += siz[v];
if(son[u] == 0 || siz[v] > siz[son[u]])
son[u] = v;
}
}
void dfs2(int u,int topx){
top[u] = topx;
dfn[u] = ++cnt;
a[dfn[u]] = w[u];
if(son[u] == 0) return;
dfs2(son[u],topx);
for(int i = h[u];i != -1;i = ne[i]){
if(e[i] == fa[u]) continue;
if(e[i] == son[u]) continue;
int v = e[i]; dfs2(v,v);
}
}
void Update_range1(int x,int y,int k){
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])
swap(x,y);
Update1(dfn[top[x]],dfn[x],k,1,n,1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
if(x != y) Update1(dfn[x]+1,dfn[y],k,1,n,1);
}
void Update_range2(int x,int y,int k){
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])
swap(x,y);
Update2(dfn[top[x]],dfn[x],k,1,n,1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
if(x != y) Update2(dfn[x]+1,dfn[y],k,1,n,1);
}
void Update_range3(int k,int w){
Update1(u[k],v[k],w,1,n,1);
}
void Query_range(int x,int y){
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])
swap(x,y);
ans = max(Getsum(dfn[top[x]],dfn[x],1,n,1),ans);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
if(x != y) ans = max(Getsum(dfn[x]+1,dfn[y],1,n,1),ans);
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n; root = 1;
memset(h,-1,sizeof(h));
for(int i = 1;i<n;i++){
cin>>u[i]>>v[i];
cin>>w[u[i]];
add(u[i],v[i]);
add(v[i],u[i]);
}
dfs1(root,0);
dfs2(root,root);
Build(1,n,1);
while(true){
string s;
int x,y,k;
cin>>s;
if(s == "Stop") break;
else if(s == "Max") cin>>x>>y, Query_range(x,y);
else if(s == "Add") cin>>x>>y>>k,Update_range2(x,y,k);
else if(s == "Cover") cin>>x>>y>>k,Update_range1(x,y,k);
else if(s == "Change") cin>>x>>k, Update_range3(x,k);
//Query_range(2,4);
}
return 0;
}