题解：
解法1：
树链剖分一下，对每条链建立一颗Splay
以宗教为第一关键字，深度为第二关键字建立
查询相当于Splay的一个区间
修改相当于删除一个节点，加入一个节点
O(nlog^2n) O(n);
解法2：
树链剖分一下，对每条链建立maxc棵权值线段树，动态开点
O(nlog^2n) O(nlogn)
问题：自己还没写过动态开点线段树
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=300009;
const int inf=1000000000;
inline int max(int a,int b){
if(a>b)return a;
else return b;
}
int n,m;
int w[maxn],c[maxn];
int father[maxn],depth[maxn],siz[maxn];
int idp[maxn],rt[maxn],ref[maxn],hson[maxn],tp[maxn];
int cntedge;
int head[maxn];
int to[maxn<<1],nex[maxn<<1];
void Addedge(int x,int y){
nex[++cntedge]=head[x];
to[cntedge]=y;
head[x]=cntedge;
}
int nn;
int fa[maxn],ch[maxn][2],sum[maxn],mx[maxn];
inline void pushup(int x){
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+w[x];
mx[x]=max(w[x],max(mx[ch[x][0]],mx[ch[x][1]]));
}
inline int son(int x){
if(ch[fa[x]][1]==x)return 1;
else return 0;
}
inline void Rotate(int &root,int x){
int y=fa[x];
int z=fa[y];
int b=son(x),c=son(y);
int a=ch[x][b^1];
if(z)ch[z][c]=x;
else root=x;
fa[x]=z;
if(a)fa[a]=y;
ch[y][b]=a;
fa[y]=x;ch[x][b^1]=y;
pushup(y);pushup(x);
}
void Splay(int &root,int x,int i){
while(fa[x]!=i){
int y=fa[x];
int z=fa[y];
if(z==i){
Rotate(root,x);
}else{
if(son(x)==son(y)){
Rotate(root,y);Rotate(root,x);
}else{
Rotate(root,x);Rotate(root,x);
}
}
}
}
inline int cmp(int x,int y){
if(c[x]<c[y])return -1;
if(c[x]>c[y])return 1;
if(depth[x]<depth[y])return -1;
if(depth[x]>depth[y])return 1;
return 0;
}
void Ins(int &root,int p){
int x=root,y=0;
while(x){
y=x;
if(cmp(x,p)>0)x=ch[x][0];
else x=ch[x][1];
}
x=p;
fa[x]=y;ch[x][0]=ch[x][1]=0;
sum[x]=mx[x]=w[x];
if(y){
if(cmp(x,y)<0)ch[y][0]=x;
else ch[y][1]=x;
}else{
root=x;
}
Splay(root,x,0);
}
void Del(int &root,int x){
Splay(root,x,0);
if(ch[x][0]==0){
root=ch[x][1];fa[ch[x][1]]=0;
}else if(ch[x][1]==0){
root=ch[x][0];fa[ch[x][0]]=0;
}else{
int p=ch[x][0];
while(ch[p][1])p=ch[p][1];
Splay(root,p,x);
ch[p][1]=ch[x][1];fa[ch[x][1]]=p;
root=p;fa[p]=0;pushup(p);
}
}
void check(int x){
if(ch[x][0])check(ch[x][0]);
cout<<c[x]<<‘ ‘<<depth[x]<<endl;
if(ch[x][1])check(ch[x][1]);
}
int Getpre(int root,int p){
int x=root,ret=0;
while(x){
if(cmp(x,p)<0){
ret=x;
x=ch[x][1];
}else{
x=ch[x][0];
}
}
return ret;
}
int Getsuf(int root,int p){
int x=root,ret=0;
while(x){
if(cmp(x,p)>0){
ret=x;
x=ch[x][0];
}else{
x=ch[x][1];
}
}
return ret;
}
void Dfs(int now,int ff){
father[now]=ff;
depth[now]=depth[ff]+1;
siz[now]=1;
for(int i=head[now];i;i=nex[i]){
if(to[i]==ff)continue;
Dfs(to[i],now);
siz[now]+=siz[to[i]];
if(siz[to[i]]>siz[hson[now]])hson[now]=to[i];
}
}
int dfsclock;
void Dfs2(int now,int toppoint){
idp[now]=++dfsclock;
ref[dfsclock]=now;
tp[now]=toppoint;
Ins(rt[toppoint],now);
if(!hson[now])return;
Dfs2(hson[now],toppoint);
for(int i=head[now];i;i=nex[i]){
if(to[i]==father[now])continue;
if(to[i]==hson[now])continue;
Dfs2(to[i],to[i]);
}
}
void ChangeC(int x,int y){
Del(rt[tp[x]],x);
c[x]=y;
Ins(rt[tp[x]],x);
}
void ChangeW(int x,int y){
Splay(rt[tp[x]],x,0);
w[x]=y;pushup(x);
}
int QueryM(int u,int v){
int tu=tp[u];
int tv=tp[v];
int ret=0;
c[nn]=c[u];
while(tu!=tv){
if(depth[tu]<depth[tv]){
swap(tu,tv);swap(u,v);
}
depth[nn]=depth[u];
int p=Getsuf(rt[tu],nn);
Splay(rt[tu],p,0);
depth[nn]=depth[tu];
p=Getpre(rt[tu],nn);
Splay(rt[tu],p,rt[tu]);
ret=max(ret,mx[ch[ch[rt[tu]][0]][1]]);
u=father[tu];tu=tp[u];
}
if(depth[u]>depth[v])swap(u,v);
depth[nn]=depth[v];
int p=Getsuf(rt[tp[u]],nn);
Splay(rt[tp[u]],p,0);
depth[nn]=depth[u];
p=Getpre(rt[tp[u]],nn);
Splay(rt[tp[u]],p,rt[tp[u]]);
ret=max(ret,mx[ch[ch[rt[tp[u]]][0]][1]]);
return ret;
}
int QueryS(int u,int v){
int tu=tp[u];
int tv=tp[v];
int ret=0;
c[nn]=c[u];
while(tu!=tv){
if(depth[tu]<depth[tv]){
swap(tu,tv);swap(u,v);
}
depth[nn]=depth[u];
int p=Getsuf(rt[tu],nn);
Splay(rt[tu],p,0);
depth[nn]=depth[tu];
p=Getpre(rt[tu],nn);
Splay(rt[tu],p,rt[tu]);
ret+=sum[ch[ch[rt[tu]][0]][1]];
u=father[tu];tu=tp[u];
}
if(depth[u]>depth[v])swap(u,v);
depth[nn]=depth[v];
int p=Getsuf(rt[tp[u]],nn);
Splay(rt[tp[u]],p,0);
depth[nn]=depth[u];
p=Getpre(rt[tp[u]],nn);
Splay(rt[tp[u]],p,rt[tp[u]]);
ret+=sum[ch[ch[rt[tp[u]]][0]][1]];
return ret;
}
int main(){
// freopen("travel.in","r",stdin);
// freopen("travel.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d%d",&w[i],&c[i]);
for(int i=1;i<=n-1;++i){
int x,y;
scanf("%d%d",&x,&y);
Addedge(x,y);
Addedge(y,x);
}
Dfs(1,0);
Dfs2(1,1);
nn=n;
for(int i=1;i<=n;++i){
if(tp[i]==i){
c[++nn]=-inf;
c[++nn]=inf;
Ins(rt[i],nn-1);
Ins(rt[i],nn);
}
}
++nn;
while(m--){
char opty[3];
int x,y;
scanf("%s",opty);
scanf("%d%d",&x,&y);
if(opty[1]==‘C‘){
ChangeC(x,y);
}
if(opty[1]==‘W‘){
ChangeW(x,y);
}
if(opty[1]==‘M‘){
printf("%d\n",QueryM(x,y));
}
if(opty[1]==‘S‘){
printf("%d\n",QueryS(x,y));
}
}
return 0;
}