旅行（树链剖分+动态开点）

旅行

果然树剖的题代码量都不小，不过还是学了一波动态开点，妙呀！

题意：给定一棵带权带颜色的树，两种操作+两种询问：
操作1：更改某个点的颜***r> 操作2：更改某个点的权值
询问1：询问 $x,y$x,y两点间与 $x$x同色的点的权值和
询问2：询问 $x,y$x,y两点间与 $x$x同色的点的最大权值

思路：

1. 树上操作先来个树剖肯定是不亏的！
2. 对于 $1e5$1e5的颜色，每种颜色开一棵线段树，但由于空间肯定开不小，因此考虑动态开点
3. 对于第一个操作，考虑现将那个点在原来颜色的树中给删掉（权值变成 $0$0就可以认为删掉了），然后再在新颜色的树中增加这个点（所有线段树操作考虑用树剖的下标）
4. 而第二个操作其实就是第一个操作的后半部分，比较简单
5. 由于询问比较简单，只有区间求和以及区间最大值，因此就不讲了。

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int N, Q;
int head[maxn], to[maxn*2], nxt[maxn*2], tot;
int top[maxn], sz[maxn], son[maxn], w[maxn], c[maxn];
int id[maxn], dp[maxn], fa[maxn], ID;
int root[maxn], ls[maxn<<8], rs[maxn<<8], cnt;
int sum[maxn<<8], mx[maxn<<8];

inline void add_edge(int u, int v) {
    ++tot, to[tot]=v, nxt[tot]=head[u], head[u]=tot;
    ++tot, to[tot]=u, nxt[tot]=head[v], head[v]=tot;
}

void dfs1(int u, int fa) {
    dp[u]=dp[fa]+1; sz[u]=1, ::fa[u]=fa;
    for(int i=head[u]; i; i=nxt[i]) {
        int v=to[i];
        if(v!=fa) {
            dfs1(v,u);
            sz[u]+=sz[v];
            if(sz[v]>sz[son[u]]) son[u]=v;
        }
    }
}

void dfs2(int u, int tp) {
    id[u]=++ID, top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    for(int i=head[u]; i; i=nxt[i]) {
        int v=to[i];
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}

inline void push_up(int now) {
    sum[now]=sum[ls[now]]+sum[rs[now]];
    mx[now]=max(mx[ls[now]],mx[rs[now]]);
}

void remove(int x, int l, int r, int now) {
    if(l==r) { sum[now]=mx[now]=0; return; }
    int m=(l+r)/2;
    if(x<=m) remove(x,l,m,ls[now]);
    else remove(x,m+1,r,rs[now]);
    push_up(now);
}

void update(int x, int d, int l, int r, int &now) {
    if(!now) now=++cnt;
    if(l==r) { sum[now]=mx[now]=d; return; }
    int m=(l+r)/2;
    if(x<=m) update(x,d,l,m,ls[now]);
    else update(x,d,m+1,r,rs[now]);
    push_up(now);
}

int qsum(int x, int y, int l, int r, int now) {
    if(!now) return 0;
    if(x<=l&&r<=y) return sum[now];
    int m=(l+r)/2, ans=0;
    if(x<=m) ans+=qsum(x,y,l,m,ls[now]);
    if(y>m) ans+=qsum(x,y,m+1,r,rs[now]);
    return ans;
}

int qmax(int x, int y, int l, int r, int now) {
    if(!now) return 0;
    if(x<=l&&r<=y) return mx[now];
    int m=(l+r)/2, ans=0;
    if(x<=m) ans=max(ans,qmax(x,y,l,m,ls[now]));
    if(y>m) ans=max(ans,qmax(x,y,m+1,r,rs[now]));
    return ans;
}

int querysum(int x, int y) {
    int ans=0, rt=root[c[x]];
    while(top[x]!=top[y]) {
        if(dp[top[x]]<dp[top[y]]) swap(x,y);
        ans+=qsum(id[top[x]],id[x],1,N,rt), x=fa[top[x]];
    }
    if(dp[x]<dp[y]) swap(x,y);
    ans+=qsum(id[y],id[x],1,N,rt);
    return ans;
}

int querymax(int x, int y) {
    int ans=0, rt=root[c[x]];
    while(top[x]!=top[y]) {
        if(dp[top[x]]<dp[top[y]]) swap(x,y);
        ans=max(ans,qmax(id[top[x]],id[x],1,N,rt)), x=fa[top[x]];
    }
    if(dp[x]<dp[y]) swap(x,y);
    ans=max(ans,qmax(id[y],id[x],1,N,rt));
    return ans;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    N=read(), Q=read();
    for(int i=1; i<=N; ++i) w[i]=read(), c[i]=read();
    for(int i=1; i<N; ++i) add_edge(read(),read());
    dfs1(1,0), dfs2(1,1);
    for(int i=1; i<=N; ++i) update(id[i],w[i],1,N,root[c[i]]);
    while(Q--) {
        char q[3]; int x, y;
        scanf("%s%d%d", q, &x, &y);
        if(q[1]=='C') {
            remove(id[x],1,N,root[c[x]]);
            update(id[x],w[x],1,N,root[c[x]=y]);
        }
        else if(q[1]=='W') update(id[x],w[x]=y,1,N,root[c[x]]);
        else if(q[1]=='S') printf("%d\n", querysum(x,y));
        else printf("%d\n", querymax(x,y));
    }
}