树剖+分块码风优美re+wa求调教（悬一关

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int nxt,to;
}e[200005];
int head[100005],cnt_edge;
void add_edge(int u,int v)
{
	e[++cnt_edge].to=v;
	e[cnt_edge].nxt=head[u];
	head[u]=cnt_edge;
}
int a[100005],c[100005];
int top[100005],size[100005],son[100005],f[100005],dep[100005],dfn[100005],cnt;
int wa[100005],wc[100005];
void dfs1(int u,int fa)
{
	f[u]=fa;
	size[u]=1;
	dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[son[u]]<size[v])
			son[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t;
	dfn[u]=++cnt;
	wa[cnt]=a[u];
	wc[cnt]=c[u];
	if(son[u])
		dfs2(son[u],t);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==f[u]||v==son[u])
			continue;
		dfs2(v,v);
	}
}
int n,m;
int siz,belong[100005],bl[100005],br[100005],bnum;
int sum_col[1145][100005];//ÿһ¿éÄÚijÑÕÉ«µÄ×ܺÍ
int max_col[1145][100005];//ÿһ¿éÄÚijÑÕÉ«µÄ×î´óÖµ 

void bld()
{
	siz=sqrt(n/log2(n));
	bnum=ceil(1.0*n/siz);
	for(int i=1;i<=bnum;i++)
	{
		bl[i]=(i-1)*siz+1;
		br[i]=i*siz;
		for(int j=bl[i];j<=br[i];j++)
			belong[j]=i;
	}
	br[bnum]=n;
	for(int i=1;i<=bnum;i++)
		for(int j=bl[i];j<=br[i];j++)
		{
			sum_col[i][wc[j]]+=wa[j];
			max_col[i][wc[j]]=max(max_col[i][wc[j]],wa[j]);
		}
}
void add_col(int x,int c)
{
	for(int i=bl[belong[x]];i<=br[belong[x]];i++)
		sum_col[belong[x]][wc[i]]=0,max_col[belong[x]][wc[i]]=0;
	wc[x]=c;
	for(int i=bl[belong[x]];i<=br[belong[x]];i++)
	{
		sum_col[belong[x]][wc[i]]+=wa[i];
		max_col[belong[x]][wc[i]]=max(max_col[belong[x]][wc[i]],wa[i]);
	}
}
void add_w(int x,int w)
{
	for(int i=bl[belong[x]];i<=br[belong[x]];i++)
		sum_col[belong[x]][wc[i]]=0,max_col[belong[x]][wc[i]]=0;
	wa[x]=w;
	for(int i=bl[belong[x]];i<=br[belong[x]];i++)
	{
		sum_col[belong[x]][wc[i]]+=wa[i];
		max_col[belong[x]][wc[i]]=max(max_col[belong[x]][wc[i]],wa[i]);
	}
}
int query(int l,int r,int x)
{
	int res=0;
	if(belong[l]==belong[r])
	{
		for(int i=l;i<=r;i++)
			if(wc[i]==x)
				res+=wa[i];
		return res;
	}
	for(int i=l;i<=br[belong[l]];i++)
		if(wc[i]==x)
			res+=wa[i];
	for(int i=bl[belong[r]];i<=r;i++)
		if(wc[i]==x)
			res+=wa[i];
	for(int i=belong[l]+1;i<=belong[r]-1;i++)
		res+=sum_col[i][x];
	return res;
}
int qmax(int l,int r,int x)
{
	int res=0;
	if(belong[l]==belong[r])
	{
		for(int i=l;i<=r;i++)
			if(wc[i]==x)
				res=max(res,wa[i]);
		return res;
	}
	for(int i=l;i<=br[belong[l]];i++)
		if(wc[i]==x)
			res=max(wa[i],res);
	for(int i=bl[belong[r]];i<=r;i++)
		if(wc[i]==x)
			res=max(wa[i],res);
	for(int i=belong[l]+1;i<=belong[r]-1;i++)
		res=max(res,max_col[i][x]);
	return res;
}
int ask_sum(int x,int y,int c)
{
	int res=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		res+=query(dfn[top[x]],dfn[x],c);
		x=f[top[x]];
	}
	if(dfn[x]>dfn[y])
		swap(x,y);
	res+=query(dfn[x],dfn[y],c);
	return res;
}
int ask_max(int x,int y,int c)
{
	int res=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		res=max(res,qmax(dfn[top[x]],dfn[x],c));
		x=f[top[x]];
	}
	if(dfn[x]>dfn[y])
		swap(x,y);
	res=max(res,qmax(dfn[x],dfn[y],c));
	return res;
}
int main()
{
//	freopen("P3313_1.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&c[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	bld();	
	string op;
	int x,y;
	while(m--)
	{
		cin>>op;
//		cout<<m<<" "<<op<<endl;
		scanf("%d%d",&x,&y);
		if(op=="CC")
			add_col(dfn[x],y);
		else if(op=="CW")
			add_w(dfn[x],y);
		else if(op=="QS")
			printf("%d\n",ask_sum(x,y,wc[x]));
		else
			printf("%d\n",ask_max(x,y,wc[x]));
	}
}