虽然这一题被划在主席树下面，但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。
树链剖分后我们考虑对每一条链，建很多棵线段树，每棵线段树表示这条链上某种颜色的情况，然后大力合并。复杂度显然是对的。
关键是如何动态开点。本质上动态开点长得就和主席树差不多（这可能是为什么这题会被放在主席树下面），但是可能存在很多细节。
另：我的线段树区间查询写成依次单点查询，居然跑到了1.2s，让我一度以为是我常数问题…甚至差点卡进去了。精彩。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline int rd(){
char ch=getchar();int r=0;
while(!isdigit(ch)){ch=getchar();}
while(isdigit(ch)){r=r*10+ch-'0';ch=getchar();}
return r;
}
const int N=100005;
inline int Max(int A,int B){
return A>B?A:B;
}
inline void Swap(int &A,int &B){
A^=B^=A^=B;
}
struct ee{
int v;
int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
inline void add(int U,int V){
Eadd(U,V);Eadd(V,U);
}
int n,m;
int val[N],clr[N],dep[N],sz[N],sn[N],fa[N],dfn[N],cnt=0,tp[N];
inline void dfs0(int X){
dep[X]=dep[fa[X]]+1;sz[X]=1;sn[X]=0;
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v==fa[X]){continue;}
fa[e[i].v]=X;
dfs0(e[i].v);
if(sz[e[i].v]>sz[sn[X]]){
sn[X]=e[i].v;
}
sz[X]+=sz[e[i].v];
}
}
inline void dfs1(int X){
dfn[X]=++cnt;
if(sn[X]){tp[sn[X]]=tp[X];dfs1(sn[X]);}
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v==sn[X]||e[i].v==fa[X]){continue;}
tp[e[i].v]=e[i].v;dfs1(e[i].v);
}
}
#define MID ((L+R)>>1)
struct Node{
int l;int r;int sm;int mx;
}tr[4000005];
int rt[N];
int tcnt=0;
inline void chg(int &NW,int L,int R,int P,int V){
if(!NW){NW=++tcnt;}
if(L==R){tr[NW].sm=V,tr[NW].mx=V;return;}
P<=MID?(chg(tr[NW].l,L,MID,P,V)):(chg(tr[NW].r,MID+1,R,P,V));
tr[NW].sm=tr[tr[NW].l].sm+tr[tr[NW].r].sm;tr[NW].mx=Max(tr[tr[NW].l].mx,tr[tr[NW].r].mx);
}
inline int qryMx(int X,int A,int B,int L,int R){
if(A>R||B<L||!X){return 0;}
if(A<=L&&B>=R){return tr[X].mx;}//此处不应写成L==R
return Max((A<=MID?qryMx(tr[X].l,A,B,L,MID):0),(B>MID?qryMx(tr[X].r,A,B,MID+1,R):0));
}
inline int qrySm(int X,int A,int B,int L,int R){
if(A>R||B<L||!X){return 0;}
if(A<=L&&B>=R){return tr[X].sm;}
return (A<=MID?qrySm(tr[X].l,A,B,L,MID):0)+(B>MID?qrySm(tr[X].r,A,B,MID+1,R):0);
}
inline void ADD(int X,int P,int V){
chg(rt[X],1,n,P,V);
}
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
val[i]=rd(),clr[i]=rd();
}
int u,v;
for(int i=1;i<n;++i){
u=rd(),v=rd();
add(u,v);
}
sz[0]=0;fa[1]=0;
dfs0(1);
tp[1]=1;
dfs1(1);
for(int i=1;i<=n;++i){
ADD(clr[i],dfn[i],val[i]);
}
char ch[10];
int x,y,c;
for(int i=1;i<=m;++i){
std::cin>>ch+1;
switch(ch[2]){
case 'C':{
x=rd(),y=rd();
ADD(clr[x],dfn[x],0);
ADD(clr[x]=y,dfn[x],val[x]);
break;
}
case 'W':{
x=rd(),y=rd();
ADD(clr[x],dfn[x],val[x]=y);
break;
}
case 'S':{
x=rd(),y=rd();
int RT=0;c=clr[x];
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
RT+=qrySm(rt[c],dfn[tp[x]],dfn[x],1,n);
x=fa[tp[x]];
}
if(dep[x]<dep[y]){Swap(x,y);}
RT+=qrySm(rt[c],dfn[y],dfn[x],1,n);
printf("%d\n",RT);
break;
}
case 'M':{
x=rd(),y=rd();
int RT=0;c=clr[x];
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
RT=Max(RT,qryMx(rt[c],dfn[tp[x]],dfn[x],1,n));
x=fa[tp[x]];
}
if(dep[x]<dep[y]){Swap(x,y);}
RT=Max(RT,qryMx(rt[c],dfn[y],dfn[x],1,n));
printf("%d\n",RT);
break;
}
}
}
}
int main(){
// freopen("33132.in","r",stdin);
// freopen("33132.ans","w",stdout);
init();
return 0;
}