MnZn 树剖 8pts 求条

#include<bits/stdc++.h>
#define L (x<<1)
#define R (x<<1|1)
using namespace std;
const int N=114514<<1;
struct node{
	int to,next,w,a;
}e[N<<1];
struct Stree{
	int l,r;
	long long sum,Max,Min;
	bool tag;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define sum(x) tree[x].sum
	#define Max(x) tree[x].Max
	#define Min(x) tree[x].Min
	#define tag(x) tree[x].tag
}tree[N<<2];

int h[N],cnt;
int n,q,u,v,k;
int a[N];
string op;

int fa[N],siz[N],dep[N],son[N],mp[N];
int dfn[N],top[N],w[N],tot;

void Link(int x,int y,int w,int a){
	e[++cnt].to=y;
	e[cnt].next=h[x];
	e[cnt].w=w;
	e[cnt].a=a;
	h[x]=cnt;
}

void up(int x){
	sum(x)=sum(L)+sum(R);
	Max(x)=max(Max(L),Max(R));
	Min(x)=min(Min(L),Min(R));
}
void spread(int x){
	if(tag(x)){
		if(l(L)!=r(L)||(l(L)==r(L)&&l(L)!=1))sum(L)=-sum(L);sum(R)=-sum(R);
		if(l(L)!=r(L)||(l(L)==r(L)&&l(L)!=1))Max(L)=-Max(L);Max(R)=-Max(R);
		if(l(L)!=r(L)||(l(L)==r(L)&&l(L)!=1))Min(L)=-Min(L);Min(R)=-Min(R);
		if(l(L)!=r(L)||(l(L)==r(L)&&l(L)!=1))swap(Max(L),Min(L));swap(Max(R),Min(R));
		if(l(L)!=r(L)||(l(L)==r(L)&&l(L)!=1))tag(L)^=1;tag(R)^=1;
		tag(x)=0;
	}
}
void build(int x,int l,int r){
	l(x)=l;
	r(x)=r;
	if(l==r){
		if(l==1){
			Max(x)=-1145;
			Min(x)=1145;
		}
		else sum(x)=Max(x)=Min(x)=w[l];
		return;
	}
	int mid=l+r>>1;
	build(L,l,mid);
	build(R,mid+1,r);
	up(x);
}
void add(int x,int i,int k){
	if(l(x)==r(x)){
		if(l(x)==1)return;
		sum(x)=k;
		Max(x)=k;
		Min(x)=k;
		return;
	}
	spread(x);
	int mid=l(x)+r(x)>>1;
	if(i<=mid)add(L,i,k);
	else add(R,i,k);
	up(x);
}
void change(int x,int l,int r){
	if(l<=l(x)&&r(x)<=r){
		if(l(x)==r(x)&&l(x)==1)return;
		sum(x)=-sum(x);
		Max(x)=-Max(x);
		Min(x)=-Min(x);
		swap(Max(x),Min(x));
		tag(x)^=1;
		return;
	}
	spread(x);
	int mid=l(x)+r(x)>>1;
	if(l<=mid)change(L,l,r);
	if(r>mid)change(R,l,r);
	up(x);
}
long long querySum(int x,int l,int r){
	if(l<=l(x)&&r(x)<=r){
		return sum(x);
	}
	spread(x);
	long long res=0;
	int mid=l(x)+r(x)>>1;
	if(l<=mid)res+=querySum(L,l,r);
	if(r>mid)res+=querySum(R,l,r);
	return res;
}
long long queryMax(int x,int l,int r){
	if(l<=l(x)&&r(x)<=r){
		return Max(x);
	}
	spread(x);
	long long res=-1145;
	int mid=l(x)+r(x)>>1;
	if(l<=mid)res=max(queryMax(L,l,r),res);
	if(r>mid)res=max(queryMax(R,l,r),res);
	return res;
}
long long queryMin(int x,int l,int r){
	if(l<=l(x)&&r(x)<=r){
		return Min(x);
	}
	spread(x);
	long long res=1145;
	int mid=l(x)+r(x)>>1;
	if(l<=mid)res=min(queryMin(L,l,r),res);
	if(r>mid)res=min(queryMin(R,l,r),res);
	return res;
}

void dfs1(int x,int father,int d){
	fa[x]=father;
	siz[x]=1;
	dep[x]=d;
	son[x]=-1;
	int maxson=0;
	for(int i=h[x];i;i=e[i].next){
		int y=e[i].to;
		if(y==father)continue;
		mp[e[i].a]=y;
		dfs1(y,x,d+1);
		siz[x]+=siz[y];
		if(siz[y]>maxson){
			son[x]=y;
			maxson=siz[y];
		}
	}
}
void dfs2(int x,int tp){
	dfn[x]=++tot;
	top[x]=tp;
	if(son[x]!=-1)dfs2(son[x],tp);
	for(int i=h[x];i;i=e[i].next){
		int y=e[i].to;
		if(y==fa[x])continue;
		if(y!=son[x])dfs2(y,y);
		if(y!=fa[x])w[dfn[y]]=e[i].w;
	}
}

void rangeA(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		change(1,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	change(1,dfn[x],dfn[y]); 
}
long long SUM(int x,int y){
	long long res=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res+=querySum(1,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	res+=querySum(1,dfn[x],dfn[y]); 
	return res;
}
long long MAX(int x,int y){
	long long res=-1145;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res=max(queryMax(1,dfn[top[x]],dfn[x]),res);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	res=max(queryMax(1,dfn[x],dfn[y]),res); 
	return res;
}
long long MIN(int x,int y){
	long long res=1145;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res=min(queryMin(1,dfn[top[x]],dfn[x]),res);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	res=min(queryMin(1,dfn[x],dfn[y]),res); 
	return res;
}

int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v>>k;
		Link(u,v,k,i);
		Link(v,u,k,i);
	}
	dfs1(0,-1,1);
	dfs2(0,0);
	build(1,1,n);
	cin>>q;
	while(q--){
		cin>>op;
		if(op=="C"){
			cin>>u>>k;
			add(1,dfn[mp[u]],k);
		}else if(op=="N"){
			cin>>u>>v;
			rangeA(u,v);
		}else if(op=="SUM"){
			cin>>u>>v;
			cout<<SUM(u,v)<<endl;
		}else if(op=="MAX"){
			cin>>u>>v;
			cout<<MAX(u,v)<<endl;
		}else{
			cin>>u>>v;
			cout<<MIN(u,v)<<endl;
		}
	}
	return 0;
}