TLE#4

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mpr make_pair
#define fr first
#define sc second
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=2e5+5,SN=605;
int n,q;
vector<int>e[N];
int dep[N],siz[N],fa[N],son[N];
int dfs(int u,int father){
	dep[u]=dep[father]+1;
	fa[u]=father;
	siz[u]=1;
	int maxn=-1;
	for (auto v:e[u]){
		if (v==father) continue;
		int sizes=dfs(v,u);
		siz[u]+=sizes;
		if (sizes>maxn) maxn=sizes,son[u]=v;
	}
	return siz[u];
}
int dfn[N],top[N],tip=1;
void dfs2(int u,int father,int op){
	if (op==1) top[u]=top[father];
	dfn[u]=tip++;
	if (son[u]!=0) dfs2(son[u],u,1);
	for (auto v:e[u]){
		if (v==father||v==son[u]) continue;
		dfs2(v,u,0);
	}
}
void init(int root){
	dfs(root,0);
	for (int i=1;i<=n;i++) top[i]=i;
	dfs2(root,0,0);
}
int _c[N],_w[N],c[N],w[N];
struct block_array{
	#define lc(x) ((x)*val-val+1)
	#define rc(x) (min(n,(x)*val))
	int val,block[N],sum[N][SN],mx[N][SN];
	void build(){
		val=sqrt(n/log2(n));
		for (int i=1;i<=n;i++) block[i]=(n-1)/val+1,mx[c[i]][block[i]]=-1e18;
		for (int i=1;i<=n;i++) sum[c[i]][block[i]]+=w[i];
		for (int i=1;i<=n;i++) mx[c[i]][block[i]]=max(mx[c[i]][block[i]],w[i]);
	}
	void cc(int x,int k){
		sum[c[x]][block[x]]-=w[x];
		sum[k][block[x]]+=w[x];
		mx[c[x]][block[x]]=-1e18;
		for (int i=lc(block[x]);i<=rc(block[x]);i++)
			if (i!=x) mx[c[i]][block[i]]=max(mx[c[i]][block[i]],w[i]);
		mx[k][block[x]]=max(mx[k][block[x]],w[x]);
		c[x]=k;
	}
	void cw(int x,int k){
		sum[c[x]][block[x]]+=k-w[x];
		w[x]=k;
		mx[c[x]][block[x]]=-1e18;
		for (int i=lc(block[x]);i<=rc(block[x]);i++)
			mx[c[i]][block[i]]=max(mx[c[i]][block[i]],w[i]);
	}
	int qs(int l,int r,int k){
//		cout<<l<<' '<<r<<' '<<k<<'\n';
		int res=0;
		if (block[l]==block[r]){
			for (int i=l;i<=r;i++) res+=(c[i]==k)*w[i];
			return res;
		}
		for (int i=l;i<=rc(block[l]);i++) res+=(c[i]==k)*w[i];
		for (int i=r;i>=lc(block[r]);i--) res+=(c[i]==k)*w[i];
		for (int i=block[l]+1;i<block[r];i++) res+=sum[k][i];
		return res;
	}
	int qm(int l,int r,int k){
		int res=-1e18;
		if (block[l]==block[r]){
			for (int i=l;i<=r;i++) if (c[i]==k) res=max(res,w[i]);
			return res;
		}
		for (int i=l;i<=rc(block[l]);i++) if (c[i]==k) res=max(res,w[i]);
		for (int i=r;i>=lc(block[r]);i--) if (c[i]==k) res=max(res,w[i]);
		for (int i=block[l]+1;i<block[r];i++) res=max(res,mx[k][i]);
		return res;
	}
	#undef lc
	#undef rc
}book;
int QS(int x,int y,int k){
	int res=0;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		res+=book.qs(dfn[top[x]],dfn[x],k);
		x=fa[top[x]];
	}
	if (dep[x]>dep[y]) swap(x,y);
	res+=book.qs(dfn[x],dfn[y],k);
	return res;
}
int QM(int x,int y,int k){
	int res=-1e18;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		res=max(res,book.qm(dfn[top[x]],dfn[x],k));
		x=fa[top[x]];
	}
	if (dep[x]>dep[y]) swap(x,y);
	res=max(res,book.qm(dfn[x],dfn[y],k));
	return res;
}
signed main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read(),q=read();
	for (int i=1;i<=n;i++){
		_w[i]=read();
		_c[i]=read();
	}
	for (int i=1;i<n;i++){
		int u=read(),v=read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	init(1);
	for (int i=1;i<=n;i++){
		c[dfn[i]]=_c[i];
		w[dfn[i]]=_w[i];
	}
//	for (int i=1;i<=n;i++) cout<<c[i]<<' ';cout<<'\n';
//	for (int i=1;i<=n;i++) cout<<w[i]<<' ';cout<<'\n';
	book.build();
	while (q--){
		string s;cin>>s;
		int x=read(),y=read();
		if (s=="CC") _c[x]=y,book.cc(dfn[x],y);
		if (s=="CW") _w[x]=y,book.cw(dfn[x],y);
		if (s=="QS") cout<<QS(x,y,_c[x])<<'\n';
		if (s=="QM") cout<<QM(x,y,_c[x])<<'\n';
	}
	return 0;
}