树剖全RE求调

#include<bits/stdc++.h>
using namespace std;
const double pi=3.14;
const int inf=0x3f3f3f3f;
const int NIL=-1;
const int MOD=1e9+7;
const int MAXN=1e5+7;
int n,c[MAXN];
struct Edge{
	int lst,v,w;
	Edge(){}
	Edge(int llst,int vv,int ww){
		lst=llst,v=vv,w=ww;
	}
}E[MAXN*2];
int head[MAXN*2],tot;
void add(int u,int v,int w){
	E[++tot]=Edge(head[u],v,w);
	head[u]=tot;
}
int siz[MAXN],hson[MAXN],fa[MAXN],dep[MAXN];
int remx[MAXN],remy[MAXN];
bool ifh[MAXN];
void DFS1(int s,int faa){
	fa[s]=faa;
	siz[s]=1;
	dep[s]=dep[faa]+1;
	int maxx=0,heav=-1;
	for (int i=head[s];~i;i=E[i].lst){
		int v=E[i].v,w=E[i].w;
		if (v==faa) continue;
		DFS1(v,s);
		siz[s]+=siz[v];
		if (siz[v]>maxx){
			maxx=siz[v];
			heav=v;
		}
	}
	hson[s]=heav;
	ifh[heav]=1;
}
int endd[MAXN],dfn[MAXN],times=0,root=1,top[MAXN];
void DFS2(int s,int faa){
	//cout<<s<<endl;
	dfn[s]=++times;
	if (s==root){
		top[s]=s;
	}else if (!ifh[s]){
		top[s]=s;
	}else if (ifh[s]){
		if (ifh[faa]){
			top[s]=top[faa];
		}else{
			top[s]=s;
		}
	}
	if (hson[s]!=-1) DFS2(hson[s],s);
	for (int i=head[s];~i;i=E[i].lst){
		int v=E[i].v,w=E[i].w;
		if (v==hson[s]) c[dfn[s]+1]=w;
		if (v==faa||v==hson[s]) continue;
		c[times+1]=w;
		DFS2(v,s); 
	}
	endd[s]=times;
}
int lazyadd[MAXN*4],T[MAXN*4],len[MAXN*4],lazycov[MAXN*4];
void pushdown(int x){
	if (~lazycov[x]){
		lazycov[x*2]=lazycov[x*2+1]=lazycov[x];
		T[x*2]=T[x*2+1]=lazycov[x]; 
		lazycov[x]=lazyadd[x]=0;
		return;
	}
	if (lazyadd[x]){
		lazyadd[x*2]+=lazyadd[x];
		lazyadd[x*2+1]+=lazyadd[x];
		T[x*2]+=lazyadd[x];
		T[x*2+1]+=lazyadd[x];
		lazyadd[x]=0;
	}
}
void pushup(int x){
	T[x]=max(T[x*2],T[x*2+1]);
}
void build(int l,int r,int x){
	len[x]=r-l+1; 
	lazycov[x]=-1;
	if (l==r){
		lazyadd[x]=0;
		T[x]=c[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
	pushup(x);
}
int query(int l,int r,int ll,int rr,int x){
	if (l>=ll&&r<=rr){
		return T[x];
	}
	int mid=(l+r)>>1;
	pushdown(x);
	if (mid<ll) return query(mid+1,r,ll,rr,x*2+1);
	else if (mid>=rr) return query(l,mid,ll,rr,x*2);
	else{
		return max(query(l,mid,ll,rr,x*2),query(mid+1,r,ll,rr,x*2+1));
	}
}
void update(int l,int r,int ll,int rr,int v,int x){
	if (l>=ll&&r<=rr){
		lazycov[x]=v;
		lazyadd[x]=0;
		T[x]=v;
		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if (mid>=rr) update(l,mid,ll,rr,v,x*2);
	else if (mid<ll) update(mid+1,r,ll,rr,v,x*2+1);
	else{
		update(l,mid,ll,rr,v,x*2);
		update(mid+1,r,ll,rr,v,x*2+1);
	}
	pushup(x);
}
void ADD(int l,int r,int ll,int rr,int v,int x){
	if (l>=ll&&r<=rr){
		lazyadd[x]+=v;
		T[x]+=v;
		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if (mid>=rr) ADD(l,mid,ll,rr,v,x*2);
	else if (mid<ll) ADD(mid+1,r,ll,rr,v,x*2+1);
	else{
		ADD(l,mid,ll,rr,v,x*2);
		ADD(mid+1,r,ll,rr,v,x*2+1);
	}
	pushup(x);
}
int QTree(int x,int y){
	int ans=0;
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if (dep[fx]<dep[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		ans=max(ans,query(1,n,dfn[fx],dfn[x],1));
		x=fa[fx];fx=top[x];
	}
	if (dfn[x]<dfn[y]+1){
		swap(fx,fy);
		swap(x,y);
	}
	ans=max(ans,query(1,n,dfn[y]+1,dfn[x],1));
	return ans;
}
void UTree(int x,int y,int z,bool opt){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if (dep[fx]<dep[fy]){
			swap(fx,fy);
			swap(x,y); 
		}
		if (opt) update(1,n,dfn[fx],dfn[x],z,1);
		else ADD(1,n,dfn[fx],dfn[x],z,1);
		x=fa[fx];fx=top[x];
	}
	if (dfn[x]<dfn[y]+1){
		swap(fx,fy);
		swap(x,y);
	}
	if (opt) update(1,n,dfn[y]+1,dfn[x],z,1);
	else ADD(1,n,dfn[y]+1,dfn[x],z,1);
}
int read()
{
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();
	memset(head,-1,sizeof(head));
	for (int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		add(u,v,w);add(v,u,w);
		remx[i]=u;remy[i]=v;
	}
	DFS1(1,0);
	ifh[1]=1;
	DFS2(1,0);
	build(1,n,1);
	string str;
	while(str!="Stop"){
		cin>>str;
		if (str=="Change"){
			int k=read(),v=read();
			if (dfn[remx[k]]+1>dfn[remy[k]]) swap(remx[k],remy[k]);
			update(1,n,dfn[remx[k]]+1,dfn[remy[k]],v,1);
		}else if (str=="Add"){
			int x=read(),y=read(),v=read();
			UTree(x,y,v,0);
		}else  if (str=="Cover"){
			int x=read(),y=read(),v=read();
			UTree(x,y,v,1);
		}else if (str=="Max"){
			int x=read(),y=read();
			cout<<QTree(x,y)<<endl;
		}
	}
}