求条玄关，马峰优良pwp

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)
#define ull unsigned long long
#define int128 __int128
#define faster ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define mid ((l+r)>>1)
using namespace std;
const int maxn=1e5+10;
int tot;
int n,q;
int root[maxn];
namespace segment_trees{
	struct node{
		int ls,rs,sumseg,maxseg;
	}nd[maxn*50];
	int newp;
	struct segment_tree{
		void pushup(int k){
			nd[k].sumseg=nd[k].maxseg=0;
			if(nd[k].ls)nd[k].sumseg+=nd[nd[k].ls].sumseg,nd[k].maxseg=max(nd[k].maxseg,nd[nd[k].ls].maxseg);
			if(nd[k].rs)nd[k].sumseg+=nd[nd[k].rs].sumseg,nd[k].maxseg=max(nd[k].maxseg,nd[nd[k].rs].maxseg);
		}
		void change(int &k,int l,int r,int x,int y){
			if(l>x||r<x)return;
			if(!k)k=++newp;
			if(l==r){
				nd[k].sumseg=nd[k].maxseg=y;
				return;
			}
			change(nd[k].ls,l,mid,x,y);
			change(nd[k].rs,mid+1,r,x,y);
			pushup(k);
		}
		int querysum(int k,int l,int r,int x,int y){
			if(!k||l>y||r<x)return 0;
			if(l>=x&&r<=y)return nd[k].sumseg;
			return querysum(nd[k].ls,l,mid,x,y)+querysum(nd[k].rs,mid+1,r,x,y);
		}
		int querymax(int k,int l,int r,int x,int y){
			if(!k||l>y||r<x)return 0;
			if(l>=x&&r<=y)return nd[k].maxseg;
			return max(querymax(nd[k].ls,l,mid,x,y),querymax(nd[k].rs,mid+1,r,x,y));
		}
	}tr[maxn];
};
using namespace segment_trees;
vector<int>g[maxn];
int dep[maxn],sz[maxn],fa[maxn];
int dfn[maxn],top[maxn],son[maxn],dfc;
void dfs1(int u,int from){
	fa[u]=from;
	sz[u]=1,son[u]=-1;
	dep[u]=dep[from]+1;
	for(int v:g[u]){
		if(v==from)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(son[u]==-1||sz[v]>sz[son[u]])son[u]=v;
	}
	return;
}
void dfs2(int u,int tp){
	dfn[u]=++dfc;
	top[u]=tp;
	if(son[u]==-1)return;
	dfs2(son[u],tp);
	for(int v:g[u])
	if(v!=son[u]&&v!=fa[u])
	dfs2(v,v);
	return;
}
int w[maxn],col[maxn];
int qsum(int u,int v,int cc){
	int ret=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		ret+=tr[cc].querysum(root[cc],1,n,dfn[top[u]],dfn[u]);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);
	ret+=tr[cc].querysum(root[cc],1,n,dfn[u],dfn[v]);
	return ret;
}
int qmax(int u,int v,int cc){
	int ret=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		ret=max(ret,tr[cc].querymax(root[cc],1,n,dfn[top[u]],dfn[u]));
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);
	ret=max(ret,tr[cc].querymax(root[cc],1,n,dfn[u],dfn[v]));
	return ret;
}
void solve(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>w[i]>>col[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	} 
	dfs1(1,1);
	dfs2(1,1);
	for(int i=1;i<=n;i++)tr[col[i]].change(root[col[i]],1,n,dfn[i],w[i]);
	while(q--){
		string opt;
		cin>>opt;
		if(opt=="CC"){
			int x,y;
			cin>>x>>y;
			tr[col[x]].change(root[col[x]],1,n,dfn[x],-w[x]);
			col[x]=y;
			tr[col[x]].change(root[col[x]],1,n,dfn[x],w[x]);
		}
		else if(opt=="CW"){
			int x,y;
			cin>>x>>y;
			tr[col[x]].change(root[col[x]],1,n,dfn[x],-w[x]);
			w[x]=y;
			tr[col[x]].change(root[col[x]],1,n,dfn[x],w[x]);
		}
		else if(opt=="QS"){
			int u,v;
			cin>>u>>v;
			cout<<qsum(u,v,col[u])<<'\n';
		}
		else{
			int u,v;
			cin>>u>>v;
			cout<<qmax(u,v,col[u])<<'\n';
		}
	}
}
signed main(){
	faster;
	int T=1;
	while(T--)solve();
}