样例本地过了评测 RE 求调

7 2
1 4
2 1
4 3
3 4
4 4
4 3
2 1
1 2
2 3
1 4
4 5
5 6
2 7
CC 4 4
QS 5 1

8

#include<bits/stdc++.h>
#define ll int
#define fir first
#define sec second
using namespace std;

vector<ll>eg[100005];
pair<ll,ll>cpo[100005];

ll n,Q,B,lit,inb[100005];
ll dep[100005],siz[100005];
ll son[100005],fas[100005];

void dfs_1(ll fa,ll p){
	dep[p]=dep[fa]+1;
	siz[p]=1;fas[p]=fa;
	for(ll v:eg[p]){
		if(v==fa)continue;
		dfs_1(p,v);
		siz[p]+=siz[v];
		if(siz[son[p]]<siz[v])son[p]=v;
	}
}

struct PIC{
	ll L,R,sm[100005],mx[100005];
	PIC(){
		memset(sm,0,sizeof(sm));
		memset(mx,0,sizeof(mx));
	}
};
struct BLK{
	ll op,len,top;
	vector<PIC>hac;
	vector<ll>pot={0},inw={0};
	void init(){
		if(pot.size()<B)op=0;
		else{
			ll p=0;
			op=1;len=pot.size()-1;
			while(1){
				PIC add;
				add.L=p+1,add.R=min(len,p+B);
//				cout<<"add.L = "<<add.L<<"   add.R = "<<add.R<<endl;
				for(ll i=add.L;i<=add.R;i++){
//					cout<<"i = "<<i<<"   pot[i] = "<<pot[i]<<"   {"<<cpo[pot[i]].fir<<","<<cpo[pot[i]].sec<<"}"<<endl;
					inw[pot[i]]=hac.size();
					add.sm[cpo[pot[i]].sec]+=cpo[pot[i]].fir;
					add.mx[cpo[pot[i]].sec]=max(add.mx[cpo[pot[i]].sec],cpo[pot[i]].fir);
				}
				hac.push_back(add);
				p=add.R;
				if(add.R==len)break;
			}
		}
	}
	inline void era(ll k){
		for(ll i=hac[k].L;i<=hac[k].R;i++){
			hac[k].sm[cpo[pot[i]].sec]=0;
			hac[k].mx[cpo[pot[i]].sec]=0;
		}
	}
	inline void add(ll k){
//		cout<<"add("<<k<<")"<<endl;
		for(ll i=hac[k].L;i<=hac[k].R;i++){
			hac[k].sm[cpo[pot[i]].sec]+=cpo[pot[i]].fir;
			hac[k].mx[cpo[pot[i]].sec]=max(hac[k].mx[cpo[pot[i]].sec],cpo[pot[i]].fir);
//			cout<<"hac["<<k<<"].sm["<<cpo[pot[i]].sec<<"] += "<<cpo[pot[i]].fir<<" = "<<hac[k].sm[cpo[pot[i]].sec]<<endl;
//			cout<<"hac["<<k<<"].mx["<<cpo[pot[i]].sec<<"] = max( "<<cpo[pot[i]].fir<<" ) = "<<hac[k].mx[cpo[pot[i]].sec]<<endl;
		}
	}
	inline void modify_1(ll p,ll k){
		if(op==1){
			era(inw[p]);
			cpo[p].fir=k;
			add(inw[p]);
		}
		else cpo[p].fir=k;
	}
	inline void modify_2(ll p,ll k){
		if(op==1){
			era(inw[p]);
			cpo[p].sec=k;
			add(inw[p]);
		}
		else cpo[p].sec=k;
	}
	inline ll pos(ll k){return lower_bound(pot.begin(),pot.end(),k)-pot.begin();}
	inline ll query_1(ll x,ll y,ll k){
		x=pos(x),y=pos(y);
		if(x>y)swap(x,y);
		ll res=0;
		if(op==1){
			for(PIC &it:hac){
				if(it.L>=x&&it.R<=y)res+=it.sm[k];
				else{
					for(ll i=it.L;i<=it.R;i++)
						if(i>=x&&i<=y&&cpo[pot[i]].sec==k)
							res+=cpo[pot[i]].fir;
				}
			}
		}
		else{
			for(ll i=x;i<=y;i++)
				if(cpo[pot[i]].sec==k)
					res+=cpo[pot[i]].fir;
		}
		return res;
	}
	inline ll query_2(ll x,ll y,ll k){
//		cout<<"query("<<x<<","<<y<<","<<k<<")"<<endl;
		x=pos(x),y=pos(y);
		if(x>y)swap(x,y);
//		cout<<"x = "<<x<<"   y = "<<y<<endl;
		ll res=0;
		if(op==1){
			for(PIC &it:hac){
//				cout<<"it = {"<<it.L<<","<<it.R<<"}"<<endl;
				if(it.L>=x&&it.R<=y){
					res=max(res,it.mx[k]);
//					cout<<"st_1 res = max("<<it.mx[k]<<") = "<<res<<endl;
				}
				else{
					for(ll i=it.L;i<=it.R;i++)
						if(i>=x&&i<=y&&cpo[pot[i]].sec==k){
							res=max(res,cpo[pot[i]].fir);
//							cout<<"st_1 res = max("<<cpo[pot[i]].fir<<") = "<<res<<endl;
						}
				}
			}
		}
		else{
			for(ll i=x;i<=y;i++)
				if(cpo[pot[i]].sec==k)
					res=max(res,cpo[pot[i]].fir);
		}
		return res;
	}
}blk[100005];

void dfs_2(ll p,ll opt){
	inb[p]=opt;
	blk[opt].pot.push_back(p);
	if(son[p])dfs_2(son[p],opt);
	for(ll v:eg[p]){
		if(v==fas[p]||v==son[p])continue;
		blk[++lit].top=v;
		dfs_2(v,lit);
	}
}

inline ll query_1(ll x,ll y,ll k){
	ll res=0;
	while(inb[x]!=inb[y]){
		if(dep[blk[inb[x]].top]<dep[blk[inb[y]].top])swap(x,y);
		res+=blk[inb[x]].query_1(blk[inb[x]].top,x,k);
		x=fas[blk[inb[x]].top];
	}
	if(dep[x]>dep[y])swap(x,y);
	res+=blk[inb[x]].query_1(x,y,k);
	return res;
}
inline ll query_2(ll x,ll y,ll k){
	ll res=0;
	while(inb[x]!=inb[y]){
		if(dep[blk[inb[x]].top]<dep[blk[inb[y]].top])swap(x,y);
//		cout<<"inb[x] = "<<inb[x]<<endl;
		res=max(res,blk[inb[x]].query_2(blk[inb[x]].top,x,k));
//		cout<<"res = max( blk["<<inb[x]<<"].query_2( "<<blk[inb[x]].top<<","<<x<<","<<k<<" )) = "<<res<<endl;
		x=fas[blk[inb[x]].top];
	}
	if(dep[x]>dep[y])swap(x,y);
//	cout<<"inb[x] = "<<inb[x]<<endl;
	res=max(res,blk[inb[x]].query_2(x,y,k));
//	cout<<"res = max( blk["<<inb[x]<<"].query_2( "<<x<<","<<y<<","<<k<<" )) = "<<res<<endl;
	return res;
}

signed main(){
//	freopen("code.in","r",stdin);
//	freopen("code.out","w",stdout);
	ios::sync_with_stdio(false);
	
	cin>>n>>Q;B=sqrt(n);
	for(ll i=1;i<=n;i++)
		cin>>cpo[i].fir>>cpo[i].sec;
	for(ll i=1;i<n;i++){
		ll x,y;cin>>x>>y;
		eg[x].push_back(y);
		eg[y].push_back(x);
	}
		
	dfs_1(0,1);
	
	blk[++lit].top=1;
	dfs_2(1,lit);
	
//	cout<<"inb : ";for(ll i=1;i<=n;i++)cout<<inb[i]<<" ";cout<<endl;
	
//	cout<<"init"<<endl;
	for(ll i=1;i<=lit;i++){
//		cout<<endl<<"i = "<<i<<endl;
//		cout<<"pot : ";for(ll it:blk[i].pot)cout<<it<<" ";cout<<endl;
		blk[i].init();
//		cout<<"op = "<<blk[i].op<<"   blk[i].hac.size() = "<<blk[i].hac.size()<<endl;
//		if(blk[i].op==1){
//			cout<<"hac : "<<endl;
//			for(PIC &it:blk[i].hac){
//				cout<<"L = "<<it.L<<"   R = "<<it.R<<endl;
//				cout<<"sm : ";for(ll q=1;q<=5;q++)cout<<it.sm[q]<<" ";cout<<endl;
//				cout<<"mx : ";for(ll q=1;q<=5;q++)cout<<it.mx[q]<<" ";cout<<endl;
//			}
//		}
	}
	
	while(Q--){
		char op;ll x,y;
		cin>>op>>op>>x>>y;
		if(op=='C')blk[inb[x]].modify_2(x,y);
		if(op=='W')blk[inb[x]].modify_1(x,y);
		if(op=='S')cout<<query_1(x,y,cpo[x].sec)<<endl;
		if(op=='M')cout<<query_2(x,y,cpo[x].sec)<<endl;
		
//		cout<<"print ==========================="<<endl;
//		for(ll i=1;i<=lit;i++){
//			cout<<endl<<"i = "<<i<<endl;
//			cout<<"pot : ";for(ll it:blk[i].pot)cout<<it<<" ";cout<<endl;
//			cout<<"op = "<<blk[i].op<<"   blk[i].hac.size() = "<<blk[i].hac.size()<<endl;
//			if(blk[i].op==1){
//				cout<<"hac : "<<endl;
//				for(PIC &it:blk[i].hac){
//					cout<<"L = "<<it.L<<"   R = "<<it.R<<endl;
//					cout<<"sm : ";for(ll q=1;q<=5;q++)cout<<it.sm[q]<<" ";cout<<endl;
//					cout<<"mx : ";for(ll q=1;q<=5;q++)cout<<it.mx[q]<<" ";cout<<endl;
//				}
//			}
//		}
		
	}
	
	return 0;
}
/*
10 10
6 6
5 3
4 3
5 3
1 3
2 1
6 7
7 5
6 7
5 3
1 2
1 3
2 4
1 5
2 6
1 7
5 8
2 9
1 10
QS 9 7
CC 8 7
CC 5 1
CC 3 7
QS 7 7
CC 5 1
CW 7 4
CC 1 5
CC 1 4
CC 6 1

*/