过切仅过样例QWQ

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define v first
#define w second
const int N=1e6+5;
string s;
bool vis[N];
int n;
vector<pair<int,int>> g[N];
int d[N],fa[N],si[N],son[N];
int Index,dfn[N],top[N],val[N];
int a[N],t[N],ad1[N],ad2[N];
int U[N],V[N];
void add1(int p) {
	if(ad1[p]) {
		t[p<<1]+=ad1[p];
		t[p<<1|1]+=ad1[p];
		ad1[p<<1]+=ad1[p];
		ad1[p<<1|1]+=ad1[p];
		ad1[p]=0;
	}
}
void add2(int p) {
	if(ad2[p]>=0) {
		t[p<<1]=ad2[p];
		t[p<<1|1]=ad2[p];
		ad2[p<<1]=ad2[p];
		ad2[p<<1|1]=ad2[p];
		ad2[p]=-1;
		ad1[p<<1]=ad2[p<<1|1]=0;
	}
}
void down(int p) {add2(p),add1(p);}
void build(int l,int r,int p) {
	ad2[p]=-1;
	if(l==r) {	t[p]=a[l];	return;	}
	int m=(l+r)>>1;
	build(l,m,p<<1);build(m+1,r,p<<1|1);
	t[p]=max(t[p<<1],t[p<<1|1]);
}
void ADD(int l,int r,int S,int T,int p,int ch) {
	if(l>=S&&r<=T) {
		t[p]+=ch,ad1[p]+=ch;
		return;
	}
	int m=(l+r)>>1;
	down(p);
	if(S<=m)	ADD(l,m,S,T,p<<1,ch);
	if(T>m)	ADD(m+1,r,S,T,p<<1|1,ch);
	t[p]=max(t[p<<1],t[p<<1|1]);
	return;
}
void COVER(int l,int r,int S,int T,int p,int ch) {
	if(l>=S&&r<=T) {
		t[p]=ch,
		ad2[p]=ch,
		ad1[p]=0;
		return;
	}
	int m=(l+r)>>1;
	down(p);
	if(S<=m)	COVER(l,m,S,T,p<<1,ch);
	if(T>m)	COVER(m+1,r,S,T,p<<1|1,ch);
	t[p]=max(t[p<<1],t[p<<1|1]);
	return;
}
int SUM(int l,int r,int S,int T,int p) {
	if(l>=S&&r<=T)	return t[p];
	int m=(l+r)>>1,sum=0;
	down(p);
	if(S<=m)	sum=SUM(l,m,S,T,p<<1);
	if(T>m)	sum=max(sum,SUM(m+1,r,S,T,p<<1|1));
	return sum;
}
void dfs1(int u,int ft) {
	d[u]=d[ft]+1,fa[u]=ft,
	si[u]=1,vis[u]=1;
	int mx=0;
	for(auto i:g[u])
		if(!vis[i.v]) {
			dfs1(i.v,u);
			si[u]+=si[i.v];
			val[i.v]=i.w;
			if(si[i.v]>mx)	son[u]=i.v,mx=si[i.v];
		}
}
void dfs2(int u,int toop) {
	vis[u]=1,top[u]=toop;
	dfn[u]=++Index,a[Index]=val[u];
	if(!son[u])	return;
	dfs2(son[u],toop);
	for(auto i:g[u])
		if(!vis[i.v]&&i.v!=fa[u]&&i.v!=son[u])	dfs2(i.v,i.v);
}
inline void change(int p,int w) {
	int cur;
	if(dfn[U[p]]>dfn[V[p]])	cur=U[p];
	else	cur=V[p];
	COVER(1,n,dfn[cur],dfn[cur],1,w);
}
inline void cover(int u,int v,int w) {
	while(top[u]!=top[v]) {
		if(d[top[u]]<d[top[v]])	swap(u,v);
		COVER(1,n,dfn[top[u]],dfn[u],1,w);
		u=fa[top[u]];
	}
	if(d[u]>d[v])	swap(u,v);
	COVER(1,n,dfn[u]+1,dfn[v],1,w);
}
inline void add(int u,int v,int w) {
	while(top[u]!=top[v]) {
		if(d[top[u]]<d[top[v]])	swap(u,v);
		ADD(1,n,dfn[top[u]],dfn[u],1,w);
		u=fa[top[u]];
	}
	if(d[u]>d[v])	swap(u,v);
	ADD(1,n,dfn[u]+1,dfn[v],1,w);
}
inline int maxx(int u,int v) {
	int res=0;
	while(top[u]!=top[v]) {
		if(d[top[u]]<d[top[v]])	swap(u,v);
		res=max(res,SUM(1,n,dfn[top[u]],dfn[u],1));
		u=fa[top[u]];
	}
	if(d[u]>d[v])	swap(u,v);
	res=max(res,SUM(1,n,dfn[u]+1,dfn[v],1));
	return res;
}
signed main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<n;++i) {
		int u,v,w;	cin>>u>>v>>w;
		U[i]=u,V[i]=v;
		g[u].push_back(make_pair(v,w)),
		g[v].push_back(make_pair(u,w));
	}
	dfs1(1,0);memset(vis,0,sizeof(vis));dfs2(1,1);
	build(1,n,1);
	while(cin>>s) {
		if(s=="Change") {
			int u,w;	cin>>u>>w;
			change(u,w);
		} else if(s=="Cover") {
			int u,v,w;	cin>>u>>v>>w;
			cover(u,v,w);
		} else if(s=="Add") {
			int u,v,w;	cin>>u>>v>>w;
			add(u,v,w);
		} else if(s=="Max") {
			int u,v;	cin>>u>>v;
			cout<<maxx(u,v)<<endl;
		} else	break;
	}
	return 0;
}