记录编号	586132	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2014]旅行	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	3.073 s
提交时间	2024-01-05 21:20:34	内存使用	78.98 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 1e5+10;
int n,m;
struct made{
    int ver,nx;
}e[N<<1];
int hd[N],tot,cnt,idx;
int fa[N],size[N],son[N],dep[N];
int dfn[N],rnk[N],top[N];
int w[N],c[N],root[N];
struct Tree{
    int ls,rs,ma,sum;
    #define ls(x) t[x].ls
    #define rs(x) t[x].rs
    #define ma(x) t[x].ma
    #define sum(x) t[x].sum
}t[N*50];
void pushup(int x){
    sum(x) = sum(ls(x)) + sum(rs(x));
    ma(x) = max(ma(ls(x)),ma(rs(x)));
}
void insert(int &x,int l,int r,int k,int z){
    if(!x)x = ++idx;
    if(l == r){
        ma(x) = z,sum(x) = z;
        return; 
    }
    int mid = l + r >> 1;
    if(k <= mid)insert(ls(x),l,mid,k,z);
    else insert(rs(x),mid+1,r,k,z);
    pushup(x);
}
int asksum(int x,int l,int r,int a,int b){
    if(!x)return 0;
    if(a <= l && r <= b)return sum(x);
    int mid = l + r >> 1,ans = 0;
    if(a <= mid)ans += asksum(ls(x),l,mid,a,b);
    if(b > mid)ans += asksum(rs(x),mid+1,r,a,b);
    return ans;
}
int askmax(int x,int l,int r,int a,int b){
    if(!x)return 0;
    if(a <= l && r <= b)return ma(x);
    int mid = l + r >> 1,ans = 0;
    if(a <= mid)ans = max(ans,askmax(ls(x),l,mid,a,b));
    if(b > mid)ans = max(ans,askmax(rs(x),mid+1,r,a,b));
    return ans;
}
//--------------------------
void add(int x,int y){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
void dfs1(int x){
    size[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(dep[y])continue;
        dep[y] = dep[x] + 1;
        fa[y] = x;
        dfs1(y);
        size[x] += size[y];
        if(!son[x] || size[y] > size[son[x]])son[x] = y;
    }
}
void dfs2(int x,int t){
    dfn[x] = ++cnt,top[x] = t;
    rnk[cnt] = x;
    if(!son[x])return;
    dfs2(son[x],t);
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y != fa[x] && y != son[x])dfs2(y,y);
    }
}
int calsum(int x,int y,int z){
    int ans = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        ans += asksum(root[z],1,n,dfn[top[x]],dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    ans += asksum(root[z],1,n,dfn[x],dfn[y]);
    return ans;
}
int calmax(int x,int y,int z){
    int ans = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        ans = max(ans,askmax(root[z],1,n,dfn[top[x]],dfn[x]));
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    ans = max(ans,askmax(root[z],1,n,dfn[x],dfn[y]));
    return ans;
}
int main(){
    freopen("SD_trip.in","r",stdin);
    freopen("SD_trip.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;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dep[1] = 1;dfs1(1),dfs2(1,1);
    for(int i = 1;i <= n;i++)insert(root[c[i]],1,n,dfn[i],w[i]);
    for(int i = 1;i <= m;i++){
        char op[4];int x,y;
        scanf("%s%d%d",op,&x,&y);
        if(op[0] == 'C'){
            if(op[1] == 'C'){
                insert(root[c[x]],1,n,dfn[x],0);
                insert(root[y],1,n,dfn[x],w[x]);
                c[x] = y;
            }
            else{
                insert(root[c[x]],1,n,dfn[x],y);
                w[x] = y;//!!!
            }
        }
        else{
            if(op[1] == 'S')printf("%d\n",calsum(x,y,c[x]));
            else printf("%d\n",calmax(x,y,c[x]));
        }
    }
    
    return 0;
    
}