存个板子。。

Problem

咕咕咕

Solution

这次线段树是用指针写的...
写法倒挺像主席树的...
差点就写成傻逼了因此还是过来存个板子...

至于主席树能不能做，因为主席树记录到根的前缀和是要整体重构的，所以对操作分块重构应该是可行的

不过算一下复杂度 $O(n\sqrt{n}\log{1e4})$ 显然应该是个错的....

Code

// Code by ajcxsu
// Problem: traveller

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10, M=2e5+10;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }


const int MM=4e6;
struct Node *nil;
struct Node {
    Node *ls, *rs;
    int s, m;
    void pup() {
        s=ls->s+rs->s;
        m=max(ls->m, rs->m);
    }
} *rt[N], po[MM], *pp=po;
void ini() {
    nil=pp++, nil->ls=nil->rs=nil, nil->s=0, nil->m=-0x3f3f3f3f;
    fill(rt, rt+N, nil);
}
void updata(Node *&x, int l, int r, int d, int v) {
    if(x==nil) x=pp++, *x=*nil;
    if(l==r) { x->s=v, x->m=v?v:-0x3f3f3f3f; return; }
    int mid=(l+r)>>1;
    if(d<=mid) updata(x->ls, l, mid, d, v);
    else updata(x->rs, mid+1, r, d, v);
    x->pup();
}
int querys(Node *x, int l, int r, int xl, int xr) {
    if(xl<=l && r<=xr) return x->s;
    int mid=(l+r)>>1, ret=0;
    if(xl<=mid) ret+=querys(x->ls, l, mid, xl, xr);
    if(xr>mid) ret+=querys(x->rs, mid+1, r, xl, xr);
    return ret;
}
int querym(Node *x, int l, int r, int xl, int xr) {
    if(xl<=l && r<=xr) return x->m;
    int mid=(l+r)>>1, ret=-0x3f3f3f3f;
    if(xl<=mid) ret=querym(x->ls, l, mid, xl, xr);
    if(xr>mid) ret=max(ret, querym(x->rs, mid+1, r, xl, xr));
    return ret;
}

int c[N], w[N], dfn[N], dep[N], fa[N], son[N], top[N], siz[N], idx;
int n, q;
void dfs1(int x=1, int k=1) {
    dep[x]=k, siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
    if(!dep[to[u]]) {
        fa[to[u]]=x, dfs1(to[u], k+1), siz[x]+=siz[to[u]];
        if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
    }
}
void dfs2(int x=1, int t=1) {
    dfn[x]=++idx, top[x]=t, updata(rt[c[x]], 1, n, dfn[x], w[x]);
    if(son[x]) dfs2(son[x], t);
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) dfs2(to[u], to[u]);
}

int paths(int s, int t) {
    Node *nd=rt[c[s]];
    int ret=0;
    while(top[s]!=top[t]) {
        if(dep[top[s]]<dep[top[t]]) swap(s, t);
        ret+=querys(nd, 1, n, dfn[top[s]], dfn[s]);
        s=fa[top[s]];
    }
    if(dep[s]>dep[t]) swap(s, t);
    return ret+querys(nd, 1, n, dfn[s], dfn[t]);
}
int pathm(int s, int t) {
    Node *nd=rt[c[s]];
    int ret=-0x3f3f3f3f;
    while(top[s]!=top[t]) {
        if(dep[top[s]]<dep[top[t]]) swap(s, t);
        ret=max(ret, querym(nd, 1, n, dfn[top[s]], dfn[s]));
        s=fa[top[s]];
    }
    if(dep[s]>dep[t]) swap(s, t);
    return max(ret, querym(nd, 1, n, dfn[s], dfn[t]));
}

int main() {
    ios::sync_with_stdio(false), ini();
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>w[i]>>c[i];
    int u, v;
    for(int i=1;i<n;i++) cin>>u>>v, ins(u, v), ins(v, u);
    dfs1(), dfs2();
    char com[3];
    while(q--) {
        cin>>com>>u>>v;
        if(com[0]=='C') {
            if(com[1]=='C') updata(rt[c[u]], 1, n, dfn[u], 0), updata(rt[c[u]=v], 1, n, dfn[u], w[u]);
            else updata(rt[c[u]], 1, n, dfn[u], w[u]=v);
        }
        else {
            if(com[1]=='S') cout<<paths(u, v)<<endl;
            else cout<<pathm(u, v)<<endl;
        }
    }
    return 0;
}