妹子刚学OI 树剖10pts在线求条

#include<iostream>
#define int long long
#define C 2147483647
#define lc p<<1
#define rc (p<<1)+1
using namespace std;
struct Tr{
	int l,r,maxn,cov,chan;
}tr[800005];
struct Edge{
	int l,w,nxt;
}edges[200005];
int n,tt,head[200005],num[200005];
int siz[200005],son[200005],fas[200005],dep[200005];
int cnt,top[200005],id[200005],di[200005],val[200005];
void add_edge(int f,int l,int w){
	tt+=1;
	edges[tt]={l,w,head[f]};
	head[f]=tt;
}
void dfs1(int x,int fa){
	fas[x]=fa,dep[x]=dep[fa]+1,siz[x]=1;
	for(int i=head[x];i;i=edges[i].nxt){
		int l=edges[i].l;
		if(l==fa) continue;
		dfs1(l,x);
		siz[x]+=siz[l],num[l]=edges[i].w;
		if(siz[l]>siz[son[x]]) son[x]=l;
	}
}
void dfs2(int x,int tot){
	cnt+=1,id[x]=cnt,di[cnt]=x,val[cnt]=num[x],top[x]=tot;
	if(!son[x]) return;
	dfs2(son[x],tot);
	for(int i=head[x];i;i=edges[i].nxt){
		int l=edges[i].l;
		if(l==son[x]||l==fas[x]) continue;
		dfs2(l,l);
	}
}
void pushup(int p){
	tr[p].maxn=max(tr[lc].maxn,tr[rc].maxn);
}
void pushdown(int p){
	if(tr[p].cov!=-1){
		tr[lc].maxn=tr[p].cov;
		tr[rc].maxn=tr[p].cov;
		tr[lc].cov=tr[p].cov;
		tr[rc].cov=tr[p].cov;
	}
	tr[lc].maxn+=tr[p].chan;
	tr[rc].maxn+=tr[p].chan;
	tr[lc].chan+=tr[p].chan;
	tr[rc].chan+=tr[p].chan;
	tr[p].chan=0,tr[p].cov=-1;
}
void build(int l,int r,int p){
	tr[p]={l,r,0,-1,0};
	if(l==r){
		tr[p].maxn=val[l];
		return;
	}
	int m=(l+r)/2;
	build(l,m,lc);build(m+1,r,rc);
	pushup(p);
}
void update_cov(int l,int r,int p,int k){
	pushdown(p);
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].cov=k,tr[p].chan=0,tr[p].maxn=k;
		return;
	}
	int m=(tr[p].l+tr[p].r)/2;
	if(l<=m) update_cov(l,r,lc,k);
	if(m<r) update_cov(l,r,rc,k);
	pushup(p);
}
void update_add(int l,int r,int p,int k){
	pushdown(p);
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].chan+=k,tr[p].maxn+=k;
		return;
	}
	int m=(tr[p].l+tr[p].r)/2;
	if(l<=m) update_add(l,r,lc,k);
	if(m<r) update_add(l,r,rc,k);
	pushup(p);
}
void update_self_cov(int x,int k){
	update_cov(id[x],id[x],1,k);
}
void update_tr_cov(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update_cov(id[top[x]],id[x],1,k);
		x=fas[top[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	if(x==y) return;
	update_cov(id[son[y]],id[x],1,k);
}
void update_tr_add(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update_add(id[top[x]],id[x],1,k);
		x=fas[top[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	if(x==y) return;
	update_add(id[son[y]],id[x],1,k);
}
int find(int l,int r,int p){
	pushdown(p);
	if(l<=tr[p].l&&tr[p].r<=r) return tr[p].maxn;
	int m=(tr[p].l+tr[p].r)/2,an=0;
	if(l<=m) an=max(an,find(l,r,lc));
	if(m<r) an=max(an,find(l,r,rc));
	return an;
}
int find_tr(int x,int y){
	int an=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		an=max(an,find(id[top[x]],id[x],1));
		x=fas[top[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	if(x==y) return an;
	an=max(an,find(id[son[y]],id[x],1));
	return an;
}
signed main(){
	string s;
	int f,l,w;
	ios::sync_with_stdio(false);
	cin.tie();cout.tie();
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>f>>l>>w;
		add_edge(f,l,w);
		add_edge(l,f,w);
	}
	dfs1(1,0);dfs2(1,1);build(1,n,1);
	while(true){
		cin>>s;
		if(s=="Stop") break;
		else if(s=="Max"){
			cin>>f>>l;
			if(f==l) cout<<0<<endl;
			else cout<<find_tr(f,l)<<endl;
		}
		else if(s=="Change"){
			cin>>f>>l;
			int awa=edges[f*2].l,ouo=edges[f*2-1].l;
			if(fas[ouo]==awa) swap(ouo,awa);
			update_self_cov(awa,l);
		}
		else if(s=="Cover"){
			cin>>f>>l>>w;
			if(f==l) continue;
			update_tr_cov(f,l,w);
		}
		else if(s=="Add"){
			cin>>f>>l>>w;
			if(f==l) continue;
			update_tr_add(f,l,w);
		}
	}
	return 0;
}