https://www.luogu.com.cn/problem/P4315
调了一下午 人裂开了
#include<bits/stdc++.h>
using namespace std;
using PII=pair<int,int>;
const int N=1e5+10,M=2*N;
int n,idx,cnt;
int e[M],ne[M],h[N],w[M],a[N],nw[N];
int fa[N],son[N],siz[N];
int dep[N],top[N],id[N];
vector<PII>p;
struct Tree{
int l,r,mx,add,c;
}tr[N*4];
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs1(int u,int father,int depth){
siz[u]=1,fa[u]=father,dep[u]=depth;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==father)continue;
a[j]=w[i];
//w[j]=w[i];把边权给点要新开个数组,这样明显是错的,没看出来,调了一下午...
dfs1(j,u,depth+1);
siz[u]+=siz[j];
if(siz[son[u]]<siz[j])son[u]=j;
}
}
void dfs2(int u,int t){
id[u]=++cnt,nw[cnt]=a[u],top[u]=t;
//nw[cnt]=w[u];
if(!son[u])return;
dfs2(son[u],t);
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==fa[u]||j==son[u])continue;
dfs2(j,j);
}
}
void pushup(int u){
tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void pushdown(int u){
auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
if(~root.c){
left.c=right.c=root.c;
left.add=right.add=0;//全部修改成一个数一定记得把"增加"懒标记清空
left.mx=right.mx=root.c;
root.c=-1;
}
if(root.add){
left.add+=root.add;
right.add+=root.add;
left.mx+=root.add;
right.mx+=root.add;
root.add=0;
}
}
void build(int u,int l,int r){
tr[u]={l,r,nw[l],0,-1};
if(l==r)return;
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void update1(int u,int l,int r,int v){//区间改
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].mx=v;
tr[u].c=v;
tr[u].add=0;//注意清空"增加"懒标记
return;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)update1(u<<1,l,r,v);
if(r>mid)update1(u<<1|1,l,r,v);
pushup(u);
}
void update2(int u,int l,int r,int v){//区间加
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].add+=v;
tr[u].mx+=v;
return;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)update2(u<<1,l,r,v);
if(r>mid)update2(u<<1|1,l,r,v);
pushup(u);
}
int query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r)return tr[u].mx;
pushdown(u);
int mx=0;
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)mx=max(mx,query(u<<1,l,r));
if(r>mid)mx=max(mx,query(u<<1|1,l,r));
return mx;
}
void update_path1(int u,int v,int k){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
update1(1,id[top[u]],id[u],k);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
update1(1,id[v]+1,id[u],k);//树枝的边权是深层的点权,高点的编号注意加1,下面同理
}
void update_path2(int u,int v,int k){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
update2(1,id[top[u]],id[u],k);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
update2(1,id[v]+1,id[u],k);
}
int query_path(int u,int v){
int res=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
res=max(res,query(1,id[top[u]],id[u]));
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
res=max(res,query(1,id[v]+1,id[u]));
return res;
}
int main(){
memset(h,-1,sizeof h);
scanf("%d",&n);
for(int i=0;i<n-1;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
p.emplace_back(a,b);
}
dfs1(1,-1,1),dfs2(1,1),build(1,1,n);
char op[10];
int u,v,x;
while(scanf("%s",op),*op!='S'){
scanf("%d",&u);
if(op[1]=='o'){
scanf("%d%d",&v,&x);
update_path1(u,v,x);
}
else if(op[1]=='d'){
scanf("%d%d",&v,&x);
update_path2(u,v,x);
}
else if(op[1]=='h'){
scanf("%d",&x);
int a=p[u-1].first,b=p[u-1].second;
if(dep[a]<dep[b])swap(a,b);//树枝的边权是深层的点权
update1(1,id[a],id[a],x);
}
else{
scanf("%d",&v);
printf("%d\n",query_path(u,v));
}
}
return 0;
}