Rt

蒟蒻样例最后一个过不去，34Pts，Wa7个点

#include<bits/stdc++.h>
const int N=1e6+10;
int tot,shabi,head[N]; 
struct node
{
  int v,next;
}e[N*2];
inline void add(register int u,register int v)
{
  e[++tot].v=v,e[tot].next=head[u],head[u]=tot; 
}
using namespace std;
int maxi[N*10],sum[N*10],root[N*10],ls[N*10],rs[N*10];
int f[N],dep[N],maxson[N],Size[N],top[N],id[N];
int wi[N],dat[N],cnt,n; 
void dfs1(int now,int fa)
{
  f[now]=fa; dep[now]=dep[fa]+1;
  maxson[now]=0;Size[now]=1; 
  for(int i=head[now];i;i=e[i].next)
  {
    int v=e[i].v;
    if(v!=fa)
    {
      dfs1(v,now); 
      Size[now]+=Size[v]; 
      if(Size[v]>Size[maxson[now]]) maxson[now]=v; 
    }
  }
}
void dfs2(int now,int topi)
{
  top[now]=topi; id[now]=++cnt;
  if(!maxson[now]) return; 
  
  dfs2(maxson[now],topi); 
  for(int i=head[now];i;i=e[i].next)
  {
    int v=e[i].v;
    if(v!=f[now]&&v!=maxson[now])
    {
      dfs2(v,v); 
    }
  }
}
void build(int &rt,int l,int r,int P, int K)
{
  if(!rt){rt=     ++cnt; }
  if(l==r) {sum[rt]=maxi[rt]=K; return ;}
  int mid=(l+r)>>1;
  if(P<=mid) build(ls[rt],l,mid,P,K);
  else build(rs[rt],mid+1,r,P,K);
  sum[rt]=sum[ls[rt]]+sum[rs[rt]];
  maxi[rt]=max(maxi[ls[rt]],maxi[rs[rt]]); 
}
void remove(int rt,int l,int r,int X)
{
  if(l==r) {maxi[rt]=sum[rt]=0; return ; }
  if(X<=((l+r)>>1)) remove(ls[rt],l,((l+r)>>1),X);
  else remove(rs[rt],((l+r)>>1)+1,r,X);
  maxi[rt]=max(maxi[ls[rt]],maxi[rs[rt]]);
  sum[rt]=sum[ls[rt]]+sum[rs[rt]]; 
}
int Mquery(int rt,int l,int r,int L,int R)
{
  if(L<=l&&R>=r){return maxi[rt];}
  int ans=0;
  if(L<=((l+r)>>1)) ans=max(ans,Mquery(ls[rt],l,((l+r)>>1),L,R));
  if(R>((l+r)>>1)) ans=max(ans,Mquery(rs[rt],((l+r)>>1)+1,r,L,R));
  return ans;
}
int Squery(int rt,int l,int r,int L,int R)
{
  if(L<=l&&R>=r){return sum[rt];}
  int ans=0;
  if(L<=((l+r)>>1)) ans+=Squery(ls[rt],l,((l+r)>>1),L,R);
  if(R>((l+r)>>1)) ans+=Squery(rs[rt],((l+r)>>1)+1,r,L,R);
  return ans;
}
int Xsum(int x,int y)
{
  int ans=0,zj=wi[y];
  while(top[x]!=top[y])
  {
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    ans+=Squery(root[zj],1,n,id[top[x]],id[x]); 
    x=f[top[x]]; 
  }
  if(dep[x]>dep[y]) swap(x,y); 
  ans+=Squery(root[zj],1,n,id[x],id[y]);
  return ans;
}
int Xmax(int x,int y)
{
  int ans=0,zj=wi[y];
  while(top[x]!=top[y])
  {
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    ans=max(ans,Mquery(root[zj],1,n,id[top[x]],id[x])); 
    x=f[top[x]]; 
  }
  if(dep[x]>dep[y]) swap(x,y); 
  ans=max(ans,Mquery(root[zj],1,n,id[x],id[y]));
  return ans;
}
/*void test(int rt,int l,int r)
{
  cout<<rt<<" "<<l<<" "<<r<<" "<<maxi[rt]<<endl;
  if(l==r||(!rt)) return ;
  test(ls[rt],l,(l+r)>>1);
  test(rs[rt],((l+r)>>1)+1,r); 
}*/
int main()
{
  int q;
  cin>>n>>q;
  for(int i=1;i<=n;++i)
  {
    cin>>dat[i]>>wi[i]; 
  }
  for(int i=1;i<n;++i)
  {
    int u,v;
    cin>>u>>v;
    add(u,v); add(v,u); 
  }
  dfs1(1,1); 
  dfs2(1,1); 
  //for(int i=1;i<=n;++i) cout<<" "<<top[i]<<" "<<maxson[i]<<endl;
  for(int i=1;i<=n;++i)
  {
    build(root[wi[i]],1,n,id[i],dat[i]); 
  }
  for(int i=1;i<=q;++i)
  {
    string opt; cin>>opt; 
    int x,y; cin>>x>>y; 
    if(opt[1]=='C')  //x改信y教
    // dat 是评级，w 是宗教
    {
      remove(root[wi[x]],1,n,id[x]);
      build(root[y],1,n,id[x],dat[x]);
      wi[x]=y;
    }
    else if(opt[1]=='W')
    {
      remove(root[wi[x]],1,n,id[x]);
      build(root[wi[x]],1,n,id[x],y);
      dat[x] = y;
    }
    else if(opt[1]='S') 
    {
      printf("%d\n",Xsum(x,y));
    }
    else printf("%d\n",Xmax(x,y));
  }
  return 0; 
}