8分求调

#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int N=2e5+10;
int dfn[N],dep[N],size[N],a[N],son[N],fa[N],top[N];
int Time;
vector<int> e[N];
struct edge{
	int u,v,w;
}E[N];
void dfs1(int u,int father){
	size[u]=1;
	int maxn=0,maxv=u;
	for(int v:e[u]){
		if(v==father)continue;
		dep[v]=dep[u]+1;
		fa[v]=u; 
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>maxn){
			maxn=size[v];
			maxv=v;
		}
	}
	son[u]=maxv;
}
void dfs2(int u,int father){
	dfn[u]=++Time;
	if(son[u]!=u){
		top[son[u]]=top[u];
		dfs2(son[u],u);
	}
	for(int v:e[u]){
		if(v==father||v==son[u])continue;
		top[v]=v;
		dfs2(v,u);
	}
}
int maxn[N<<2],minn[N<<2],sum[N<<2];
bool lazy[N<<2];
int w[N];
int n;
void add(int k){
	lazy[k]^=1;
	sum[k]=-sum[k];
	maxn[k]=-maxn[k];
	minn[k]=-minn[k];
	swap(maxn[k],minn[k]);			
}
void pushdown(int k){
	if(!lazy[k])return;
	add(k<<1);
	add(k<<1|1);
}
void pushup(int k){
	sum[k]=sum[k<<1]+sum[k<<1|1];
	maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
	minn[k]=min(minn[k<<1],minn[k<<1|1]);
}
void change1(int k,int l,int r,int pos,int v){
	if(l==r){
		sum[k]=minn[k]=maxn[k]=v;
		return;
	}
	pushdown(k);
	int mid=l+r>>1;
	if(pos<=mid)change1(k<<1,l,mid,pos,v);
	else change1(k<<1|1,mid+1,r,pos,v);
	pushup(k);
}
void change2(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		add(k);
		return;
	}
	pushdown(k);
	int mid=l+r>>1;
	if(x<=mid)change2(k<<1,l,mid,x,y);
	if(y>mid)change2(k<<1|1,mid+1,r,x,y);
	pushup(k);
}
int query1(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return maxn[k];
	pushdown(k);
	int mid=l+r>>1,ans=-10000001;
	if(x<=mid)ans=max(ans,query1(k<<1,l,mid,x,y));
	if(y>mid)ans=max(ans,query1(k<<1|1,mid+1,r,x,y));
	pushup(k);
	return ans;
}
int query2(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return minn[k];
	pushdown(k);
	int mid=l+r>>1,ans=10000001;
	if(x<=mid)ans=min(ans,query2(k<<1,l,mid,x,y));
	if(y>mid)ans=min(ans,query2(k<<1|1,mid+1,r,x,y));
	pushup(k);
	return ans;
}
int query3(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return sum[k];
	pushdown(k);
	int mid=l+r>>1,ans=0;
	if(x<=mid)ans+=query3(k<<1,l,mid,x,y);
	if(y>mid)ans+=query3(k<<1|1,mid+1,r,x,y);
	pushup(k);
	return ans;
}
int Q1(int x,int y){
	int ans=-10000001;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,query1(1,1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	if(x==y)return ans;
	if(dep[x]>dep[y])swap(x,y);
	return max(ans,query1(1,1,n,dfn[x]+1,dfn[y]));
}
int Q2(int x,int y){
	int ans=10000001;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=min(ans,query2(1,1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	if(x==y)return ans;
	if(dep[x]>dep[y])swap(x,y);
	return min(ans,query2(1,1,n,dfn[x]+1,dfn[y]));
}
int Q3(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans+=query3(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(x==y)return ans;
	if(dep[x]>dep[y])swap(x,y);
	return ans+query3(1,1,n,dfn[x]+1,dfn[y]);
}
void change(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		change2(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(x==y)return;
	if(dep[x]>dep[y])swap(x,y);
	change2(1,1,n,dfn[x]+1,dfn[y]);
}
int main(){
	cin>>n;
	for(int i=1;i<n;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[u+1].push_back(v+1);
		e[v+1].push_back(u+1);
		E[i]={u+1,v+1,w};
	}
	dep[1]=1;
	dfs1(1,0);
	top[1]=1;
	dfs2(1,0);
	for(int i=1;i<n;++i)change1(1,1,n,dep[E[i].u]>dep[E[i].v]?dfn[E[i].u]:dfn[E[i].v],E[i].w);
	int m;
	for(cin>>m;m;--m){
		string s;
		cin>>s;
		int x,y;
		scanf("%d%d",&x,&y);
		if(s=="C")change1(1,1,n,dep[E[x].u]>dep[E[x].v]?dfn[E[x].u]:dfn[E[x].v],y);;
		if(s=="N")change(x+1,y+1);
		if(s=="MAX")printf("%d\n",Q1(x+1,y+1));
		if(s=="MIN")printf("%d\n",Q2(x+1,y+1));
		if(s=="SUM")printf("%d\n",Q3(x+1,y+1));
	}
	return 0;
}