只AC#11玄关求条

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int n,root=1,tot,now,q;
vector<int>v(N),idx(N),idy(N),add(N<<2),temp(N),sum(N<<2),mul(N<<2),maxx(N<<2),minn(N<<2),head(N);
vector<int>dfn(N),rnk(N),siz(N),dep(N),fa(N),son(N),top(N);
string opt;
struct edge{
	int to,nxt,d;
}e[N<<1];
void add1(int u,int v,int d){
	e[++tot].to=v;
	e[tot].d=d;
	e[tot].nxt=head[u];
	head[u]=tot;
}
int dfs1(int u,int f){
	siz[u]=1;
	int p=0;
	for(int i=head[u];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==f)continue;
		fa[to]=u;
		dep[to]=dep[u]+1;
		temp[to]=e[i].d;
		siz[u]+=dfs1(to,u);
		if(siz[p]<siz[to])p=to;
	}
	son[u]=p;
	return siz[u];
}
void dfs2(int u,int tp){
	dfn[u]=++now;
	v[now]=temp[u];
	rnk[now]=u;
	top[u]=tp;
	int sn=son[u];
	if(sn&&sn!=fa[u])dfs2(sn,tp);
	for(int i=head[u];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==fa[u]||to==sn)continue;
		dfs2(to,to);
	}
}
void build(int k,int l,int r){
	mul[k]=1;
	if(l==r){
		sum[k]=v[l];
		maxx[k]=v[l];
		minn[k]=v[l];
		return;
	}
	int mid=l+(r-l)/2;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	sum[k]=sum[k<<1]+sum[k<<1|1];
	maxx[k]=max(maxx[k<<1],maxx[k<<1|1]);
	minn[k]=min(minn[k<<1],minn[k<<1|1]);
	return;
}
void pushdown(int k,int l,int r){
	if(mul[k]==1)return;
	int mid=l+(r-l)/2;
	maxx[k<<1]*=mul[k];maxx[k<<1|1]*=mul[k];
	minn[k<<1]*=mul[k];minn[k<<1|1]*=mul[k];
	sum[k<<1]*=mul[k];sum[k<<1|1]*=mul[k];
	swap(maxx[k<<1],minn[k<<1]);
	swap(maxx[k<<1|1],minn[k<<1|1]);
	mul[k]=1;
	return;
}
void change(int k,int l,int r,int x,int v){
	if(l==r){
		sum[k]=v;
		maxx[k]=v;
		minn[k]=v;
		return;
	}
	int mid=l+(r-l)/2;
	pushdown(k,l,r);
	if(x<=mid)change(k<<1,l,mid,x,v);
	else change(k<<1|1,mid+1,r,x,v);
	sum[k]=sum[k<<1]+sum[k<<1|1];
	maxx[k]=max(maxx[k<<1],maxx[k<<1|1]);
	minn[k]=min(minn[k<<1],minn[k<<1|1]);
	return;
}
void changem(int k,int l,int r,int x,int y,int v){
	if(x<=l&&r<=y){
		sum[k]*=v;
		mul[k]*=v;
		maxx[k]*=v;
		minn[k]*=v;
		swap(maxx[k],minn[k]);
		return;
	}
	int mid=l+(r-l)/2;
	pushdown(k,l,r);
	if(x<=mid)changem(k<<1,l,mid,x,y,v);
	if(y>mid)changem(k<<1|1,mid+1,r,x,y,v);
	sum[k]=sum[k<<1]+sum[k<<1|1];
	maxx[k]=max(maxx[k<<1],maxx[k<<1|1]);
	minn[k]=min(minn[k<<1],minn[k<<1|1]);
	return;
}
int seeks(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return sum[k];
	int mid=l+(r-l)/2;
	pushdown(k,l,r);
	int res=0;
	if(x<=mid)res+=seeks(k<<1,l,mid,x,y);
	if(y>mid)res+=seeks(k<<1|1,mid+1,r,x,y);
	return res;
}
int seekmx(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return maxx[k];
	int mid=l+(r-l)/2;
	pushdown(k,l,r);
	int res=-2147483647;
	if(x<=mid)res=max(res,seekmx(k<<1,l,mid,x,y));
	if(y>mid)res=max(res,seekmx(k<<1|1,mid+1,r,x,y));
	return res;
}
int seekmn(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return minn[k];
	int mid=l+(r-l)/2;
	pushdown(k,l,r);
	int res=2147483647;
	if(x<=mid)res=min(res,seekmn(k<<1,l,mid,x,y));
	if(y>mid)res=min(res,seekmn(k<<1|1,mid+1,r,x,y));
	return res;
}
int solves(int a,int b){
	int res=0;
	while(top[a]!=top[b]){
		if(dep[top[a]]<dep[top[b]])swap(a,b);
		res+=seeks(1,1,n,dfn[top[a]],dfn[a]);
		a=fa[top[a]];
	}
	if(dep[a]>dep[b])swap(a,b);
	if(a!=b)res+=seeks(1,1,n,dfn[a]+1,dfn[b]);
	return res;
}
int solvemx(int a,int b){
	int res=-2147483647;
	while(top[a]!=top[b]){
		if(dep[top[a]]<dep[top[b]])swap(a,b);
		res=max(res,seekmx(1,1,n,dfn[top[a]],dfn[a]));
		a=fa[top[a]];
	}
	if(dep[a]>dep[b])swap(a,b);
	if(a!=b)res=max(res,seekmx(1,1,n,dfn[a]+1,dfn[b]));
	return res;
}
int solvemn(int a,int b){
	int res=2147483647;
	while(top[a]!=top[b]){
		if(dep[top[a]]<dep[top[b]])swap(a,b);
		res=min(res,seekmn(1,1,n,dfn[top[a]],dfn[a]));
		a=fa[top[a]];
	}
	if(dep[a]>dep[b])swap(a,b);
	if(a!=b)res=min(res,seekmn(1,1,n,dfn[a]+1,dfn[b]));
	return res;
}
int main(){
//	freopen("P1505_1.in","r",stdin);
//	freopen("hh.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,to,d;
		cin>>u>>to>>d;
		u++;to++;
		add1(u,to,d);
		add1(to,u,d);
		idx[i]=u;idy[i]=to;
	}
	top[root]=root;
	fa[root]=-1;
	dep[root]=1;
	dfs1(root,-1);
	dfs2(root,root);
	build(1,1,n);
	cin>>q;
	while(q--){
		cin>>opt;
		if(opt=="C"){
			int x,w;
			cin>>x>>w;
			int tmp;
			if(dep[idx[x]]>dep[idy[x]])tmp=idx[x];
			else tmp=idy[x];
			change(1,1,n,dfn[tmp],w);
		}
		if(opt=="N"){
			int a,b;
			cin>>a>>b;
			a++;b++;
			while(top[a]!=top[b]){
				if(dep[top[a]]<dep[top[b]])swap(a,b);
				changem(1,1,n,dfn[top[a]],dfn[a],-1);
				a=fa[top[a]];
			}
			if(dep[a]>dep[b])swap(a,b);
			if(a!=b)changem(1,1,n,dfn[a]+1,dfn[b],-1);
		}
		if(opt=="SUM"){
			int a,b;
			cin>>a>>b;
			a++;b++;
			cout<<solves(a,b)<<endl;
		}
		if(opt=="MAX"){
			int a,b;
			cin>>a>>b;
			a++;b++;
			cout<<solvemx(a,b)<<endl;
		}
		if(opt=="MIN"){
			int a,b;
			cin>>a>>b;
			a++;b++;
			cout<<solvemn(a,b)<<endl;
		}
	}
	return 0;
}