$树链剖分 + 动态开点线段树$
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <unordered_map>
using namespace std;
const int N = 100010, M = 200010, INF = 2e9;
struct node {
int s[2];
int mxv, sum;
} tr[N * 17];
int root[N], tr_idx;
int n, m;
int h[N], e[M], ne[M], g_idx;
int W[N], C[N];
int id[N], cnt;
int depth[N], fa[N], son[N], sz[N], top[N];
void add(int a, int b)
{
e[g_idx] = b, ne[g_idx] = h[a], h[a] = g_idx ++;
}
void dfs1(int u, int p, int dep)
{
sz[u] = 1, fa[u] = p, depth[u] = dep;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == p) continue;
dfs1(j, u, dep + 1);
sz[u] += sz[j];
if(sz[son[u]] < sz[j]) son[u] = j;
}
}
void dfs2(int u, int t)
{
id[u] = ++ cnt, top[u] = t;
if(son[u] == 0) return;
dfs2(son[u], t);
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == son[u] || j == fa[u]) continue;
dfs2(j, j);
}
}
void pushup(int u)
{
tr[u].sum = tr[tr[u].s[0]].sum + tr[tr[u].s[1]].sum;
tr[u].mxv = max(tr[tr[u].s[0]].mxv, tr[tr[u].s[1]].mxv);
}
int modify(int u, int l, int r, int x, int val)
{
if(!u) u = ++ tr_idx;
if(l == r)
{
tr[u].sum += val;
tr[u].mxv = tr[u].sum;
return u;
}
int mid = l + r >> 1;
if(x <= mid) tr[u].s[0] = modify(tr[u].s[0], l, mid, x, val);
else tr[u].s[1] = modify(tr[u].s[1], mid + 1, r, x, val);
pushup(u);
return u;
}
int query(int u, int l, int r, int L, int R, int type)
{
if(!u) return 0;
if(l >= L && r <= R)
{
if(type) return tr[u].mxv;
else return tr[u].sum;
}
int mid = l + r >> 1;
int res = 0;
if(type) res = -INF;
if(L <= mid)
{
if(type) res = max(res, query(tr[u].s[0], l, mid, L, R, type));
else res += query(tr[u].s[0], l, mid, L, R, type);
}
if(R > mid)
{
if(type) res = max(res, query(tr[u].s[1], mid + 1, r, L, R, type));
else res += query(tr[u].s[1], mid + 1, r, L, R, type);
}
return res;
}
// type = 0, 求和
int query_path(int u, int v, int type)
{
int res = 0;
if(type) res = -INF;
int x = C[u];
while(top[u] != top[v])
{
if(depth[top[u]] < depth[top[v]]) swap(u, v);
if(type) res = max(res, query(root[x], 1, n, id[top[u]], id[u], type));
else res += query(root[x], 1, n, id[top[u]], id[u], type);
u = fa[top[u]];
}
if(depth[u] < depth[v]) swap(u, v);
if(type) res = max(res, query(root[x], 1, n, id[v], id[u], type));
else res += query(root[x], 1, n, id[v], id[u], type);
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d%d", &W[i], &C[i]);
memset(h, -1, sizeof h);
for(int i = 2; i <= n; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs1(1, -1, 1);
dfs2(1, 1);
for(int i = 1; i <= n; i ++) root[C[i]] = modify(root[C[i]], 1, n, id[i], W[i]);
while(m --)
{
char op[10];
scanf("%s", op);
if(strcmp(op, "CC") == 0)
{
int x, c;
scanf("%d%d", &x, &c);
int pc = C[x];
root[pc] = modify(root[pc], 1, n, id[x], -W[x]);
root[c] = modify(root[c], 1, n, id[x], W[x]);
C[x] = c;
}
else if(strcmp(op, "CW") == 0)
{
int x, w;
scanf("%d%d", &x, &w);
root[C[x]] = modify(root[C[x]], 1, n, id[x], w - W[x]);
W[x] = w;
}
else if(strcmp(op, "QS") == 0)
{
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", query_path(x, y, 0));
}
else if(strcmp(op, "QM") == 0)
{
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", query_path(x, y, 1));
}
}
return 0;
}