题目大意：给你一棵树，每个点有一个分类和一个值。有四种操作：

1. 修改某个点的分类
2. 修改某个点的值
3. 查询两个分类相同的点的最短路上，与这两个点分类相同的所有点的值的和
4. 查询两个分类相同的点的最短路上，与这两个点分类相同的所有点的值的最大值

题解：树链剖分，对每一个分类建一棵动态开点线段树就好了。

卡点：1.询问是传根写成了传编号

 

C++ Code：

#include 
     
      #define maxn 100010#define N 100010 * 4 * 20using namespace std;int n, Q;int w[maxn], c[maxn];inline int max(int a, int b) {return a > b ? a : b;}inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}int head[maxn], cnt;struct Edge {    int to, nxt;} e[maxn << 1];void add(int a, int b) {    e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;}int sz[maxn], fa[maxn], dep[maxn], son[maxn];int top[maxn], dfn[maxn], idx;void dfs1(int rt) {    sz[rt] = 1;    for (int i = head[rt]; i; i = e[i].nxt) {        int v = e[i].to;        if (!dep[v]) {            dep[v] = dep[rt] + 1;            fa[v] = rt;            dfs1(v);            sz[rt] += sz[v];            if (!son[rt] || sz[v] > sz[son[rt]]) son[rt] = v;        }     }}void dfs2(int rt) {    dfn[rt] = ++idx;    int v = son[rt];    if (v) top[v] = top[rt], dfs2(v);    for (int i = head[rt]; i; i = e[i].nxt) {        v = e[i].to;        if (v != fa[rt] && v != son[rt]) {            top[v] = v;            dfs2(v);        }    }}int root[maxn], M[N], S[N];int rc[N], lc[N], tot;void add(int &rt, int l, int r, int p, int num) {    if (!rt) rt = ++tot;    if (l == r) {        S[rt] = M[rt] = num;        return ;    }    int mid = l + r >> 1;    if (p <= mid) add(lc[rt], l, mid, p, num);    else add(rc[rt], mid + 1, r, p, num);    M[rt] = max(M[lc[rt]], M[rc[rt]]);    S[rt] = S[lc[rt]] + S[rc[rt]];}int askM(int rt, int l, int r, int L, int R) {    if (!rt || l > r || L > R) return 0;    if (L <= l && R >= r) return M[rt];    int mid = l + r >> 1, ans = 0;    if (L <= mid) ans = askM(lc[rt], l, mid, L, R);    if (R > mid) ans = max(ans, askM(rc[rt], mid + 1, r, L, R));    return ans;}int askS(int rt, int l, int r, int L, int R) {    if (!rt || l > r || L > R) return 0;    if (L <= l && R >= r) return S[rt];    int mid = l + r >> 1, ans = 0;    if (L <= mid) ans = askS(lc[rt], l, mid, L, R);    if (R > mid) ans += askS(rc[rt], mid + 1, r, L, R);    return ans;}int queryM(int rt, int x, int y) {    int ans = 0;    while (top[x] != top[y]) {        if (dep[top[x]] < dep[top[y]]) swap(x, y);        ans = max(ans, askM(rt, 1, n, dfn[top[x]], dfn[x]));        x = fa[top[x]];    }    if (dep[x] > dep[y]) swap(x, y);    ans = max(ans, askM(rt, 1, n, dfn[x], dfn[y]));    return ans;}int queryS(int rt, int x, int y) {    int ans = 0;    while (top[x] != top[y]) {        if (dep[top[x]] < dep[top[y]]) swap(x, y);        ans += askS(rt, 1, n, dfn[top[x]], dfn[x]);        x = fa[top[x]];    }    if (dep[x] > dep[y]) swap(x, y);    ans += askS(rt, 1, n, dfn[x], dfn[y]);    return ans;}int main() {    scanf("%d%d", &n, &Q);    for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &c[i]);    for (int i = 1; i < n; i++) {        int a, b;        scanf("%d%d", &a, &b);        add(a, b);        add(b, a);    }    dep[top[1] = 1] = 1;    dfs1(1);    dfs2(1);    for (int i = 1; i <= n; i++) add(root[c[i]], 1, n, dfn[i], w[i]);    while (Q --> 0) {        char op[10];        int x, y;        scanf("%s%d%d", op, &x, &y);        if (op[1] == 'C') {            add(root[c[x]], 1, n, dfn[x], 0);            c[x] = y;            add(root[y], 1, n, dfn[x], w[x]);        }        if (op[1] == 'W') {            w[x] = y;            add(root[c[x]], 1, n, dfn[x], y);        }        if (op[1] == 'S') {            printf("%d\n", queryS(root[c[x]], x, y));        }        if (op[1] == 'M') {            printf("%d\n", queryM(root[c[x]], x, y));        }    }    return 0;}