树链剖分板子

#include<bits/stdc++.h>
using namespace std; 
#define x first
#define y second
#define int long long
typedef long long ll;
const int N=100010;
struct node{
   
	int l;
	int r;
	int sum;
	int maxv;
}tr[N*20]; 
int n;
int w[N],col[N],dfn[N],h[N],ne[N*2],idx,e[N*2],top[N],son[N],sz[N],fa[N];
int cnt,tot;
int dep[N];
void add(int a,int b)
{
   
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int q;
int root[N]; 
void dfs1(int u,int f,int d)
{
   
	sz[u]=1;
	fa[u]=f;
	dep[u]=d;
	int maxd=-1;
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(j==f )	continue;
		dfs1(j,u,d+1);
		sz[u]+=sz[j];
		if(sz[j]>maxd)
		{
   
			maxd=sz[j];
			son[u]=j;
		}
	}
}
void dfs2(int u,int tp)
{
   
	top[u]=tp;
	dfn[u]=++tot;
	if(!son[u])	return ;
	dfs2(son[u],tp);
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(j==fa[u]|| son[u]==j)	continue;
		dfs2(j,j);
	}
}
void pushup(int u)
{
   
	tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum;
	tr[u].maxv=max(tr[tr[u].l].maxv,tr[tr[u].r].maxv);
}
void insert(int u,int l,int r,int pos,int x)
{
   
	if(l==r)
	{
   
		tr[u].maxv=x;
		tr[u].sum=x;
		return ;
	}
	int mid=l+r>>1;
	if(pos<=mid)
	{
   
		if(!tr[u].l)
		tr[u].l=++cnt;
		insert(tr[u].l,l,mid,pos,x);
	}
	else if(pos>mid)
	{
   
		if(!tr[u].r)
		tr[u].r=++cnt;
		insert(tr[u].r,mid+1,r,pos,x);
	}
	pushup(u);
}
void del(int u,int l,int r,int pos)
{
   
	if(!u)	return;
	if(l==r)
	{
   
		tr[u]={
   0,0,0,0};
		return ;
	}
	int mid=l+r>>1;
	if(pos<=mid)
	del(tr[u].l,l,mid,pos);
	else
	del(tr[u].r,mid+1,r,pos);	
	pushup(u);
}
void mdf(int u,int l,int r,int pos,int val)
{
   
	if(l==r)
	{
   
		tr[u].maxv=val;
		tr[u].sum=val;
		return ;
	}
	int mid=l+r>>1;
	if(pos<=mid)
	{
   
		if(!tr[u].l)
		tr[u].l=++cnt;
		mdf(tr[u].l,l,mid,pos,val);
	}
	else
	{
   
		if(!tr[u].r)
		tr[u].r=++cnt;
		mdf(tr[u].r,mid+1,r,pos,val);
	}
	pushup(u);
}
// node query(int u,int L,int R,int l,int r)
// {
   
// if(!u)
// return {0,0,0,0};
// if(L>=l && R<=r)
// return tr[u];
// int mid=L+R>>1;
// if(r<=mid) return query(tr[u].l,L,mid,l,r);
// else if(l>mid) return query(tr[u].r,mid+1,R,l,r);
// else
// {
   
// node a=query(tr[u].l,L,mid,l,r);
// node b=query(tr[u].r,mid+1,R,l,r);
// node c;
// c.maxv=max(a.maxv,b.maxv);
// c.sum=a.sum+b.sum;
// return c;
// }
// } 
int querymax(int u, int left, int right, int l, int r)
{
   
    if(!u)  return 0;
    if(left >= l and right <= r)  return tr[u].maxv;

    int res = 0;
    int mid = left + right >> 1;
    if(l <= mid)  res = querymax(tr[u].l, left, mid, l, r);
    if(r > mid)  res = max(res, querymax(tr[u].r, mid + 1, right, l, r));
    return res;
}
int querysum(int u, int left, int right, int l, int r)
{
   
    if(!u)  return 0;
    if(left >= l and right <= r)  return tr[u].sum;

    int res = 0;
    int mid = left + right >> 1;
    if(l <= mid)  res += querysum(tr[u].l, left, mid, l, r);
    if(r > mid)  res += querysum(tr[u].r, mid + 1, right, l, r);
    return res;
}
int qrsum(int u,int x,int y)
{
   
	int res=0;
	while(top[x]!=top[y])
	{
   
		if(dep[top[x]]<dep[top[y]])
		swap(x,y);
		res+=querysum(u,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
	swap(x,y);
	res+=querysum(u,1,n,dfn[x],dfn[y]);
	return	res;
}
int qrmaxv(int u,int x,int y)
{
   
	int res=0;
	while(top[x]!=top[y])
	{
   
		if(dep[top[x]]<dep[top[y]])
		swap(x,y);
		res=max(res,querymax(u,1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
	swap(x,y);
	res=max(res,querymax(u,1,n,dfn[x],dfn[y]));
	return	res;
}
signed main()
{
   
	scanf("%lld%lld", &n, &q);
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++)
	scanf("%lld%lld",&w[i],&col[i]);
	for(int i=0;i<n-1;i++)
	{
   
		int	a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	dfs1(1,0,1);
	dfs2(1,1);
	for(int i=1;i<=n;i++)
	{
   
	    if(!root[col[i]])
		root[col[i]]=++cnt;
		insert(root[col[i]],1,n,dfn[i],w[i]);
	}
	while(q--)
	{
   
		char op[3];
		int x,y;
		scanf("%s",op);
		scanf("%lld%lld",&x,&y);
		if(op[1]=='C')
		{
   
			del(root[col[x]],1,n,dfn[x]);
		// mdf(root[col[x]],1,n,dfn[x],0);
			col[x]=y;
			if(!root[y])
			root[y]=++cnt;
			mdf(root[y],1,n,dfn[x],w[x]);
		}
		else if(op[1]=='W')
		{
   
		    w[x]=y;
			mdf(root[col[x]],1,n,dfn[x],y);
		}
		else if(op[1]=='S') //求总和 
		{
   
		    printf("%lld\n",qrsum(root[col[x]],x,y));
		}
		else //求最大值 
		{
   
		    printf("%lld\n",qrmaxv(root[col[x]],x,y));
		}
	}
	return 0;
}