求调树剖

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int head[N],id[N],siz[N],cnt,top[N],fa[N],son[N],wt[N],w[N],a[N],dep[N],n,m,ecnt;
struct edge {
	int next,to,val;
} e[N<<1];
void add(int u,int v,int d) {
	e[++ecnt]= {head[u],v,d};
	head[u]=ecnt;
}
struct node {
	int l,r,sum,maxx,minx,tag;
	node operator +(const node &x)const {
		return {l,x.r,sum+x.sum,max(maxx,x.maxx),min(minx,x.minx),0};
	}
} tree[N<<2];
#define pushup(now) tree[now]=tree[now<<1]+tree[now<<1|1]
void build(int now,int l,int r) {
	if(l==r) {
		tree[now]={l,r,wt[l],wt[l],wt[l],0};
		return ;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	pushup(now);
}
void apply(int now,int tag) {
	if(tag==0)
		return ;
	tree[now].sum=-tree[now].sum;
	int Max=tree[now].maxx,Min=tree[now].minx;
	tree[now].maxx=-Min;
	tree[now].minx=-Max;
}
void givetag(int now,int tag) {
	tree[now].tag=tree[now].tag^tag;
	apply(now,tag);
}
void pushdown(int now) {
	if(tree[now].tag==0)
		return ;
	givetag(now<<1,tree[now].tag);
	givetag(now<<1|1,tree[now].tag);
	tree[now].tag=0;
}
void modify1(int now,int l,int r,int v) {
	if(tree[now].l!=tree[now].r)
		pushdown(now);
	if(tree[now].l==l&&tree[now].r==r) {
		tree[now]= {l,r,v,v,v,0};
		return ;
	}
	int mid=(tree[now].l+tree[now].r)>>1;
	if(l<=mid)
		modify1(now<<1,l,r,v);
	if(r>mid)
		modify1(now<<1|1,l,r,v);
	pushup(now);
}
void modify(int now,int l,int r,int v) {
	if(tree[now].l!=tree[now].r)
		pushdown(now);
	if(l<=tree[now].l&&tree[now].r<=r) {
		givetag(now,v);
		return ;
	}
	int mid=(tree[now].l+tree[now].r)>>1;
	if(l<=mid)
		modify(now<<1,l,r,v);
	if(r>mid)
		modify(now<<1|1,l,r,v);
	pushup(now);
}
node query(int now,int l,int r) {
	if(tree[now].l!=tree[now].r)
		pushdown(now);
	if(l<=tree[now].l&&tree[now].r<=r)
		return tree[now];
	int mid=(tree[now].l+tree[now].r)>>1;
	if(l<=mid&&r>mid)
		return tree[now<<1]+tree[now<<1|1];
	if(l<=mid)
		return tree[now<<1];
	if(r>mid)
		return tree[now<<1|1];
}
void dfs1(int x,int father,int deep) {
	dep[x]=deep;
	fa[x]=father;
	siz[x]=1;
	int maxson=-1;
	for(int i=head[x]; i; i=e[i].next) {
		int v=e[i].to;
		if(v==father)
			continue;
		w[v]=e[i].val;
//		cout<<'('<<x<<" "<<v<<" "<<w[x]<<")"<<endl;
		dfs1(v,x,deep+1);
		siz[x]+=siz[v];
		if(siz[v]>maxson) {
			maxson=v;
			son[x]=v;
		}
	}
}
void dfs2(int x,int topf) {
	id[x]=++cnt;
	wt[cnt]=w[x];
//	cout<<"&"<<wt[cnt]<<"&"<<x<<endl;
	top[x]=topf;
	if(!son[x])
		return ;
	dfs2(son[x],topf);
	for(int i=head[x]; i; i=e[i].next) {
		int v=e[i].to;
		if(v==fa[x]||v==son[x])
			continue;
		dfs2(v,v);
	}
}
node qrange(int x,int y) {
	node ans= {0,0,0,-100000,100000,0};
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		ans=ans+query(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
//	cout<<"["<<x<<" "<<y<<"]"<<endl;
	if(dep[x]>dep[y])
		swap(x,y);
//	cout<<"["<<x<<" "<<y<<"]"<<endl;
//	cout<<id[x]<<" "<<id[y]<<endl;
	ans=ans+query(1,id[x]+1,id[y]);
	return ans;
}
void mrange(int x,int y,int k) {
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		modify(1,id[top[x]],id[x],k);
		x=fa[top[x]];
	}

	if(dep[x]>dep[y])
		swap(x,y);
//	cout<<"["<<x<<" "<<y<<"]"<<endl;
//	cout<<id[x]<<" "<<id[y]<<endl;
	modify(1,id[x]+1,id[y],k);
}
void mrange1(int x,int y,int k) {
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		modify1(1,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	modify1(1,id[x]+1,id[y],k);
}
pair<int,int> E[N<<1];
int main() {
	cin>>n;
	for(int i=1; i<n; i++) {
		int x,y,z;
		cin>>x>>y>>z;
		E[i].first=x;
		E[i].second=y;
		add(x,y,z);
		add(y,x,z);
	}
	dfs1(0,0,1);
	dfs2(0,0);
	build(1,1,n);
	cin>>m;
	for(int i=1; i<=m; i++) {
		string opt;
		int x,y;
		cin>>opt>>x>>y;
		if(opt=="C")
			mrange1(E[x].first,E[x].second,y);
		if(opt=="N")
			mrange(x,y,1);
		if(opt=="SUM")
			cout<<qrange(x,y).sum<<endl;
		if(opt=="MAX")
			cout<<qrange(x,y).maxx<<endl;
		if(opt=="MIN")
			cout<<qrange(x,y).minx<<endl;
//		cout<<qrange(0,n-1).sum<<" "<<qrange(0,n-1).maxx<<" "<<qrange(0,n-1).minx<<endl;
	}
}