题目链接：传送门

Description

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

Hint

N，Q < =10^5 ， C < =10^5

Sample Input

5 6 3 1 2 3 1 2 3 3 5 1 1 2 1 3 3 4 3 5 QS 1 5 CC 3 1 QS 1 5 CW 3 3 QS 1 5 QM 2 4

Sample Output

8 9 11 3

Solution

先树链剖分一下，然后对于每一种教建一颗线段树维护Sum和Max即可

Code

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 100000 + 100;

int Begin[Maxn * 2], To[Maxn * 2], Next[Maxn * 2], e;
int dep[Maxn], fa[Maxn], top[Maxn], son[Maxn], size[Maxn];
int W[Maxn], C[Maxn];
int dfn[Maxn], idfn[Maxn], Index;
int N, M;

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

inline void dfs (int x)
{
    size[x] = 1;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (fa[x] == y) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs(y);
        size[x] += size[y];
        if (size[y] > size[son[x]]) son[x] = y;
    }
}

inline void dfs (int x, int now)
{
    dfn[x] = ++Index;
    idfn[Index] = x;
    top[x] = now;
    if (son[x]) dfs(son[x], now);
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (fa[x] == y || son[x] == y) continue;
        dfs(y, y);
    }
}

int Root[Maxn], Cnt;
struct tree
{
    int lson, rson, Max, sum;
}Tree[Maxn * 20];

inline void push_up (int &root)
{
    Tree[root].Max = max(Tree[Tree[root].lson].Max, Tree[Tree[root].rson].Max);
    Tree[root].sum = Tree[Tree[root].lson].sum + Tree[Tree[root].rson].sum;
    if (!Tree[root].lson && !Tree[root].rson)
        Tree[root].Max = Tree[root].sum = 0, root = 0;
}

inline void Insert (int &root, int l, int r, int x, int d)
{
    if (!root) root = ++ Cnt;
    if (l == r)
    {
        Tree[root].Max = Tree[root].sum = d;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) Insert(Tree[root].lson, l, mid, x, d);
    else Insert(Tree[root].rson, mid + 1, r, x, d);
    push_up(root);
}

inline void Delete (int &root, int l, int r, int x)
{
    if (l == r)
    {
        Tree[root].lson = Tree[root].rson = Tree[root].Max = Tree[root].sum = 0;
        root = 0;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) Delete(Tree[root].lson, l, mid, x);
    else Delete(Tree[root].rson, mid + 1, r, x);
    push_up(root);
}

inline void Modify1 (int x, int y)
{
    Delete(Root[C[x]], 1, N, dfn[x]);
    C[x] = y;
    Insert(Root[C[x]], 1, N, dfn[x], W[x]);
}

inline void Modify2 (int x, int y)
{
    W[x] = y;
    Insert(Root[C[x]], 1, N, dfn[x], W[x]);
}

inline int query_sum (int root, int l, int r, int x, int y)
{
    if (y < l || x > r) return 0;
    if (x <= l && r <= y) return Tree[root].sum;
    int Ans = 0;
    int mid = (l + r) >> 1;
    if (x <= mid) Ans += query_sum(Tree[root].lson, l, mid, x, y);
    if (y > mid) Ans += query_sum(Tree[root].rson, mid + 1, r, x, y);
    return Ans;
}

inline int Query1 (int x, int y)
{
    int t1 = top[x], t2 = top[y];
    int tmp = C[x];
    int Sum = 0;
    while (t1 != t2)
    {
        if (dep[t1] < dep[t2]) swap(x, y), swap(t1, t2);
        Sum += query_sum(Root[tmp], 1, N, dfn[t1], dfn[x]);
        x = fa[t1];
        t1 = top[x];
    }
    if (dep[x] < dep[y]) Sum += query_sum(Root[tmp], 1, N, dfn[x], dfn[y]);
    else Sum += query_sum(Root[tmp], 1, N, dfn[y], dfn[x]);
    return Sum;
}

inline int query_max (int root, int l, int r, int x, int y)
{
    if (y < l || x > r) return 0;
    if (x <= l && r <= y) return Tree[root].Max;
    int mid = (l + r) >> 1;
    int Max = -0x3f3f3f3f;
    if (x <= mid) Max = max(Max, query_max(Tree[root].lson, l, mid, x, y));
    if (y > mid) Max = max(Max, query_max(Tree[root].rson, mid + 1, r, x, y));
    return Max;
}

inline int Query2 (int x, int y)
{
    int t1 = top[x], t2 = top[y];
    int tmp = C[x];
    int Max = -0x3f3f3f3f;
    while (t1 != t2)
    {
        if (dep[t1] < dep[t2]) swap(x, y), swap(t1, t2);
        Max = max(Max, query_max(Root[tmp], 1, N, dfn[t1], dfn[x]));
        x = fa[t1];
        t1 = top[x];
    }
    if (dep[x] < dep[y]) Max = max(Max, query_max(Root[tmp], 1, N, dfn[x], dfn[y]));
    else Max = max(Max, query_max(Root[tmp], 1, N, dfn[y], dfn[x]));
    return Max;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) scanf("%d%d", &W[i], &C[i]);

    int x, y;
    for (int i = 1; i < N; ++i)
    {
        scanf("%d%d", &x, &y);
        add_edge(x, y);
        add_edge(y, x);
    }

    dep[1] = 1;
    dfs(1);
    dfs(1, 1);

    for (int i = 1; i <= N; ++i)
        Insert(Root[C[i]], 1, N, dfn[i], W[i]);

    char s[3];
    for (int i = 1; i <= M; ++i)
    {
        scanf("%s%d%d", s, &x, &y);
        if (s[1] == 'S') printf("%d\n", Query1(x, y));
        else if (s[1] == 'M') printf("%d\n", Query2(x, y));
        else if (s[1] == 'C') Modify1(x, y);
        else Modify2(x, y);
    }
    return 0;
}