#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);
}
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]);
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;
}
京公网安备 11010502036488号