感觉复杂度很正确，然而我的两个 ask 函数跑得贼慢。就算不跑线段树都有 400ms

#include<bits/stdc++.h>
#include<cstdio>
#define N 100100
#define pushup(now) a[now].sum=a[a[now].lson].sum+a[a[now].rson].sum,a[now].mmax=max(a[a[now].lson].mmax,a[a[now].rson].mmax)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,q;
int w[N],c[N];
vector<int>b[N];
int fa[N],siz[N],son[N],dep[N],top[N],seg[N],rev[N];
struct tree{
    int lson,rson,sum,mmax;
}a[N<<4];
int cnt=0,root[N];
inline void modify(int l,int r,int &now,int x,int v){
    if(!now)now=++cnt;
    if(l==r){a[now].sum=a[now].mmax=v;return ;}
    int mid=l+r>>1;
    if(x<=mid)modify(l,mid,a[now].lson,x,v);
    else modify(mid+1,r,a[now].rson,x,v);
    pushup(now);
    return ;
}
inline int query_sum(int l,int r,int now,int x,int y){
    if(!now)return 0;
    if(l>=x&&r<=y)return a[now].sum;
    int mid=l+r>>1,ans=0;
    if(x<=mid)ans=query_sum(l,mid,a[now].lson,x,y);
    if(y>mid)ans+=query_sum(mid+1,r,a[now].rson,x,y);
    return ans;
}
inline int query_max(int l,int r,int now,int x,int y){
    if(!now)return 0;
    if(l>=x&&r<=y)return a[now].mmax;
    int mid=l+r>>1,ans=0;
    if(x<=mid)ans=query_max(l,mid,a[now].lson,x,y);
    if(y>mid)ans=max(query_max(mid+1,r,a[now].rson,x,y),ans);
    return ans;
}
inline void dfs1(int now,int f){
    fa[now]=f;
    dep[now]=dep[f]+1;
    siz[now]=1;
    for(int i=0;i<b[now].size();i++)
        if(b[now][i]!=f){
            dfs1(b[now][i],now);
            siz[now]+=siz[b[now][i]];
            if(siz[b[now][i]>siz[son[now]]])son[now]=b[now][i];
        }
    return ;
}
inline void dfs2(int now,int Top){
    top[now]=Top;
    seg[now]=++seg[0];
    rev[seg[0]]=now;
    modify(1,n,root[c[now]],seg[0],w[now]);
    if(son[now])dfs2(son[now],Top);
    for(int i=0;i<b[now].size();i++)
        if(b[now][i]!=son[now]&&b[now][i]!=fa[now])
            dfs2(b[now][i],b[now][i]);
    return ;
}
inline int asksum(int x,int y){
    int sum=0,C=c[x];
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        sum+=query_sum(1,n,root[C],seg[top[x]],seg[x]);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    sum+=query_sum(1,n,root[C],seg[y],seg[x]);
    return sum;
}
inline int askmax(int x,int y){
    int MAX=0,C=c[x];
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        MAX=max(MAX,query_max(1,n,root[C],seg[top[x]],seg[x]));
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    MAX=max(MAX,query_max(1,n,root[C],seg[y],seg[x]));
    return MAX;
}
int main(){
	// freopen("P3313_5.in","r",stdin);
	// freopen("P3313_5.ans","w",stdout);
    n=read();q=read();
    for(int i=1;i<=n;i++)w[i]=read(),c[i]=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        b[u].push_back(v);
        b[v].push_back(u);
    }
    dfs1(1,1);dfs2(1,1);
    while(q--){
        string op;cin>>op;
        if(op=="CC"){
            int x=read(),cc=read();
            modify(1,n,root[c[x]],seg[x],0);
            modify(1,n,root[cc],seg[x],w[x]);
            c[x]=cc;
        }
        if(op=="CW"){
            int x=read(),ww=read();
            modify(1,n,root[c[x]],seg[x],ww);
            w[x]=ww;
        }
        if(op=="QS"){
            int x=read(),y=read();
            printf("%d\n",asksum(x,y));
        }
        if(op=="QM"){
            int x=read(),y=read();
            printf("%d\n",askmax(x,y));
        }
    }
    return 0;
}