难度：省选/NOI-

题目描述

        S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。
        为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
        在S国的历史上常会发生以下几种事件：

  • “CC x c“：城市x的居民全体改信了c教；
  • “CW x w“：城市x的评级调整为w;
  • “QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
  • “QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。

        由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

输入格式

        输入的第一行包含整数N，Q依次表示城市数和事件数，N、Q≤100000。
        接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。 接下来N-1行每行两个整数x，y表示一条双向道路。
        接下来Q行，每行一个操作，格式如上所述。

输出格式

        对每个QS和QM事件，输出一行，表示旅行者记下的数字。

题解

        首先肯定需要树链剖分，但答案的统计是按照种类来的，只开一棵线段树没法处理。
        于是考虑给每一个信仰开一棵线段树，但是这样直接爆内存。于是考虑动态加点，舍弃线段树的堆式储存，这样就可以开得动线段树。
        于是树链剖分+动态加点线段树就能切掉本题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>

#define  N 100005
using namespace std;
struct Edge {
    int to, next;
} edge[N << 1];

struct Node {
    int l, r, max, sum;
} nd[N << 7];

int head[N], n, q, pj[N], xy[N], dep[N], sz[N], fa[N], son[N], top[N], ct = 1;
int id[N], idhs[N], ID = 1, root[N];
char opt[50];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void ms(Node &a, Node x, Node y) {
    a.max = max(x.max, y.max), a.sum = x.sum + y.sum;
}

void DFS(int x) {
    sz[x] = 1;
    int ff = 0;
    for (int i = head[x]; i; i = edge[i].next) {
        if (sz[edge[i].to] == 0) {
            fa[edge[i].to] = x, dep[edge[i].to] = dep[x] + 1, DFS(edge[i].to), sz[x] += sz[edge[i].to];
            if (ff < sz[edge[i].to])ff = sz[edge[i].to], son[x] = edge[i].to;
        }
    }
}

void DFS(int x, int tp) {
    top[x] = tp, id[x] = ID, idhs[ID] = x, ++ID;
    if (son[x])DFS(son[x], tp);
    else return;
    for (int i = head[x]; i; i = edge[i].next)if (!id[edge[i].to])DFS(edge[i].to, edge[i].to);
}

void del(int rt, int v, int L = 1, int R = n) {//删除某一个点
    if (L == R) {
        nd[rt].sum = nd[rt].max = 0;
        return;
    }
    int mid = (L + R) >> 1;
    if (v > mid)del(nd[rt].r, v, mid + 1, R);
    else del(nd[rt].l, v, L, mid);
    ms(nd[rt], nd[nd[rt].l], nd[nd[rt].r]);
}

void ins(int &rt, int v, int L = 1, int R = n) {//插入某一个点
    if (rt == 0)rt = ct++;
    if (L == R) {
        nd[rt].sum = nd[rt].max = pj[idhs[v]];
        return;
    }
    int mid = (L + R) >> 1;
    if (v <= mid)ins(nd[rt].l, v, L, mid);
    else ins(nd[rt].r, v, mid + 1, R);
    ms(nd[rt], nd[nd[rt].l], nd[nd[rt].r]);
}

Node qu(int rt, int l, int r, int L = 1, int R = n) {//查询
    if (rt == 0)return nd[0];
    if (L >= l && R <= r)return nd[rt];
    int mid = (L + R) >> 1;
    if (l > mid)return qu(nd[rt].r, l, r, mid + 1, R);
    else if (r <= mid)return qu(nd[rt].l, l, r, L, mid);
    Node ss;
    ms(ss, qu(nd[rt].l, l, mid, L, mid), qu(nd[rt].r, mid + 1, r, mid + 1, R));
    return ss;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)scanf("%d%d", &pj[i], &xy[i]);
    for (int i = 1, x, y; i < n; i++)scanf("%d%d", &x, &y), add(x, y), add(y, x);
    dep[1] = 1, DFS(1), DFS(1, 1);//树剖过程
    for (int i = 1; i <= n; i++)ins(root[xy[i]], id[i]);
    while (q--) {
        int x, y, s;
        scanf("%s%d%d", opt, &x, &y);
        if (opt[0] == 'C' && opt[1] == 'C')del(root[xy[x]], id[x]), ins(root[xy[x] = y], id[x]);
        else if (opt[0] == 'C' && opt[1] == 'W')pj[x] = y, ins(root[xy[x]], id[x]);
        else {
            Node ans;
            ans.sum = ans.max = 0, s = xy[x];
            while (top[x] != top[y]) {
                if (dep[top[x]] > dep[top[y]])swap(x, y);
                ms(ans, ans, qu(root[s], id[top[y]], id[y])), y = fa[top[y]];
            }
            if (dep[x] > dep[y])swap(x, y);
            ms(ans, ans, qu(root[s], id[x], id[y]));
            if (opt[1] == 'S')printf("%d\n", ans.sum);
            else printf("%d\n", ans.max);
        }
    }
    return 0;
}