RT

代码如下:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int MAXN=2e5+10;
struct node
{
	int SUM,MAX,MIN;
}tree[MAXN*8];
struct Node
{
	int lst,v,w;	
}e[MAXN*2];
int head[MAXN],cnt;
int tag_b[MAXN*8];
int sz[MAXN],son[MAXN],topfa[MAXN];
int idx[MAXN],deep[MAXN],fa[MAXN];
bool used[MAXN];
int tot;
int n,m;
inline void push_down(int rt,int l,int r)
{
	if(tag_b[rt]==0) return ;
	int t=-tree[rt].MAX;
	tree[rt].MAX=-tree[rt].MIN;
	tree[rt].MIN=t;
	tree[rt].SUM=-tree[rt].SUM;
	tag_b[rt*2]^=1;
	tag_b[rt*2+1]^=1;
	tag_b[rt]=0;
	return ;
}
inline void push_up(int rt,int l,int r)
{
	int mid=(l+r)/2;
	push_down(rt,l,r);
	push_down(rt*2,l,mid);
	push_down(rt*2+1,mid+1,r);
	tree[rt].SUM=tree[rt*2].SUM+tree[rt*2+1].SUM;
	tree[rt].MAX=max(tree[rt*2].MAX,tree[rt*2+1].MAX);
	tree[rt].MIN=min(tree[rt*2].MIN,tree[rt*2+1].MIN);
	return ;
}
void update_a(int rt,int l,int r,int p,int x)
{
	push_down(rt,l,r);
	if(l==r) 
	{
		tree[rt].MAX=x;
		tree[rt].MIN=x;
		tree[rt].SUM=x;
		return ;
	}
	int mid=(l+r)/2;
	if(p<=mid) update_a(rt*2,l,mid,p,x);
	else update_a(rt*2+1,mid+1,r,p,x);
	push_up(rt,l,r);
	return ;
}
void update_b(int rt,int l,int r,int L,int R)
{
	push_down(rt,l,r);
	if(L<=l && r<=R)
	{
		tag_b[rt]^=1;
		return ;
	}
	int mid=(l+r)/2;
	if(L<=mid) update_b(rt*2,l,mid,L,R);
	if(R>mid) update_b(rt*2+1,mid+1,r,L,R);
	push_up(rt,l,r);
	return ;
}
int query_sum(int rt,int l,int r,int L,int R)
{
	push_down(rt,l,r);
	if(L<=l && r<=R) return tree[rt].SUM;
	int mid=(l+r)/2;
	int ans=0;
	if(L<=mid) ans+=query_sum(rt*2,l,mid,L,R);
	if(R>mid) ans+=query_sum(rt*2+1,mid+1,r,L,R);
	return ans;
}
int query_max(int rt,int l,int r,int L,int R)
{
	push_down(rt,l,r);
	if(L<=l && r<=R) return tree[rt].MAX;
	int mid=(l+r)/2;
	int ans=-3000;
	if(L<=mid) ans=max(ans,query_max(rt*2,l,mid,L,R));
	if(R>mid) ans=max(ans,query_sum(rt*2+1,mid+1,r,L,R));
	return ans;
}
int query_min(int rt,int l,int r,int L,int R)
{
	push_down(rt,l,r);
	if(L<=l && r<=R) return tree[rt].MIN;
	int mid=(l+r)/2;
	int ans=3000;
	if(L<=mid) ans=min(ans,query_min(rt*2,l,mid,L,R));
	if(R>mid) ans=min(ans,query_min(rt*2+1,mid+1,r,L,R));
	return ans;
}
inline void Add(int u,int v,int w)
{
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].lst=head[u];
	head[u]=cnt;
	return ;
}
void DFS1(int now,int lst,int depth)
{
	deep[now]=depth;
	fa[now]=lst;
	sz[now]=1;
	for(int i=head[now];i;i=e[i].lst)
	{
		int v=e[i].v;
		if(v==lst) continue;
		DFS1(v,now,depth+1);
		sz[now]+=sz[v];
		if(sz[v]>sz[son[now]]) son[now]=v;
	}
	return ;
}
void DFS2(int now,int lst,int top)
{
	if(now==0) return ;
	topfa[now]=top;
	used[now]=true;
	idx[now]=++tot;
	DFS2(son[now],now,top);
	for(int i=head[now];i;i=e[i].lst)
	{
		int v=e[i].v;
		if(v==lst || used[v]) continue;
		DFS2(v,now,v);
	}
	return ;
}
inline void update_range(int x,int y)
{
	while(topfa[x]!=topfa[x])
	{
		int fax=topfa[x],fay=topfa[y];
		if(deep[fay]>deep[fax])
		{
			swap(fax,fay);
			swap(x,y);
		}
		update_b(1,1,n,idx[fax],idx[x]);
		x=fa[fax];
	}
	if(deep[y]>deep[x]) swap(x,y);
	update_b(1,1,n,idx[y]+1,idx[x]);
	return ;
}
inline int query_range_sum(int x,int y)
{
	int ans=0;
	while(topfa[x]!=topfa[y])
	{
		int fax=topfa[x],fay=topfa[y];
		if(deep[fay]>deep[fax])
		{
			swap(fax,fay);
			swap(x,y);
		}
		ans+=query_sum(1,1,n,idx[fax],idx[x]);
		x=fa[fax];
	}
	if(deep[y]>deep[x]) swap(x,y);
	ans+=query_sum(1,1,n,idx[y]+1,idx[x]);
	return ans;
}
inline int query_range_max(int x,int y)
{
	int ans=-3000;
	while(topfa[x]!=topfa[y])
	{
		int fax=topfa[x],fay=topfa[y];
		if(deep[fay]>deep[fax])
		{
			swap(fax,fay);
			swap(x,y);
		}
		ans=max(ans,query_max(1,1,n,idx[fax],idx[x]));
		x=fa[fax];
	}
	if(deep[y]>deep[x]) swap(x,y);
	ans=max(ans,query_max(1,1,n,idx[y]+1,idx[x]));
	return ans;
}
inline int query_range_min(int x,int y)
{
	int ans=3000;
	while(topfa[x]!=topfa[y])
	{
		int fax=topfa[x],fay=topfa[y];
		if(deep[fay]>deep[fax])
		{
			swap(fax,fay);
			swap(x,y);
		}
		ans=min(ans,query_min(1,1,n,idx[fax],idx[x]));
		x=fa[fax];
	}
	if(deep[y]>deep[x]) swap(x,y);
	ans=min(ans,query_min(1,1,n,idx[y]+1,idx[x]));
	return ans;
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		u++,v++;
		Add(u,v,w);
		Add(v,u,w);
	}
	DFS1(1,0,1);
	DFS2(1,0,1);
	for(int i=1;i<n;i++)
	{
		int x=deep[e[i*2-1].v]<deep[e[i*2].v]?e[i*2].v:e[i*2-1].v;
		update_a(1,1,n,idx[x],e[i*2].w);
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		string op;
		cin>>op;
		if(op=="C")
		{
			int x,w;
			cin>>x>>w;
			int v=deep[e[x*2-1].v]<deep[e[x*2].v]?e[x*2].v:e[x*2-1].v;
			update_a(1,1,n,idx[v],w);
		}
		if(op=="N")
		{
			int u,v;
			cin>>u>>v;
			u++,v++;
			update_range(u,v);
		}
		if(op=="SUM")
		{
			int u,v;
			cin>>u>>v;
			u++,v++;
			cout<<query_range_sum(u,v)<<"\n";
		}
		if(op=="MAX")
		{
			int u,v;
			cin>>u>>v;
			u++,v++;
			cout<<query_range_max(u,v)<<"\n";
		}
		if(op=="MIN")
		{
			int u,v;
			cin>>u>>v;
			u++,v++;
			cout<<query_range_min(u,v)<<"\n";
		}
	}
	return 0;
}