题目： [SDOI2014] 旅行

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int INF = 0x7fffffff;
const int N = 100010;
int id[N], root[N];
int cnt;

struct Treenode {
	int l, r;
	int lc, rc;
	int maxn, sum;
} t[N << 8];

inline int newnode(int l, int r) {
	int p = ++cnt;
	t[p].l = l;
	t[p].r = r;
	return p;
}

inline void maintain(int p) {
	t[p].sum = t[t[p].lc].sum + t[t[p].rc].sum;
	t[p].maxn = max (t[t[p].lc].maxn, t[t[p].rc].maxn);
}

void build(int p, int k, int val) {
	if (t[p].l == t[p].r) {
		t[p].sum = t[p].maxn = val;
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	if (k <= mid) {
		if (!t[p].lc) t[p].lc = newnode(t[p].l, mid);
		build(t[p].lc, k, val);
	} else {
		if (!t[p].rc) t[p].rc = newnode(mid + 1, t[p].r);
		build(t[p].rc, k, val);
	}
	maintain(p);
}

void update(int p, int x, int k) {
	if (t[p].l == t[p].r) {
		t[p].sum = t[p].maxn = k;
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	if (x <= mid) update(t[p].lc, x, k);
	else update(t[p].rc, x, k);
	maintain(p);
}

int query_sum(int p, int l, int r) {
	if (p == 0) return 0;
	if (l <= t[p].l and t[p].r <= r) return t[p].sum;
	int mid = (t[p].l + t[p].r) >> 1, res = 0;
	if (l <= mid) res += query_sum(t[p].lc, l, r);
	if (r > mid) res += query_sum(t[p].rc, l, r);
	return res;
}

int query_max(int p, int l, int r) {
	if (p == 0) return 0;
	if (l <= t[p].l and t[p].r <= r) return t[p].maxn;
	int mid = (t[p].l + t[p].r) >> 1, res = -INF;
	if (l <= mid) res = max (res, query_max(t[p].lc, l, r));
	if (r > mid) res = max (res, query_max(t[p].rc, l, r));
	return res;
}

int w[N], c[N], fa[N], dep[N], son[N], top[N], size[N];
vector <int> g[N];
int n, q, tot;

void dfs1(int x, int father) {
	fa[x] = father;
	dep[x] = dep[father] + 1;
	size[x] = 1;
	int maxn = 0;
	for (int i = 0; i < g[x].size(); i++) {
		int v = g[x][i];
		if (v == father) continue;
		dfs1(v, x);
		size[x] += size[v];
		if (size[v] > maxn) {
			maxn = size[v];
			son[x] = v;
		}
	}
}

void dfs2(int x, int topnode) {
	top[x] = topnode;
	id[x] = ++tot;
	build(root[c[x]], id[x], w[x]);
	if (son[x] == 0) return;
	dfs2(son[x], topnode);
	for (int i = 0; i < g[x].size(); i++) {
		int v = g[x][i];
		if (v == son[x] or v == fa[x]) continue;
		dfs2(v, v);
	}
}

void query_sum_path(int x, int y) {
	int ans = 0;
	int b = c[x];
	while(top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans += query_sum(root[c[x]], id[top[x]], id[x]);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	cout << ans + query_sum(root[c[x]], id[x], id[y]) << endl; 
}

void query_max_path(int x, int y) {
	int ans = 0;
	int b = c[x];
	while(top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans = max (ans, query_max(root[c[x]], id[top[x]], id[x]));
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	cout << max (ans, query_max(root[c[x]], id[x], id[y])) << endl; 
}

int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); 
	cout.tie(0);
	cin >> n >> q;  
	for (int i = 1; i <= N - 10; i++) root[i] = newnode(1, n);
	for (int i = 1; i <= n; i++) cin >> w[i] >> c[i];
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	while (q--) {
		string st;
		int x, y;
		cin >> st >> x >> y;
		if (st == "CC") build(root[c[x]], id[x], 0), c[x] = y, build(root[y], id[x], w[x]);
		if (st == "CW") w[x] = y, update(root[c[x]], id[x], y);
		if (st == "QS") query_sum_path(x, y);
		if (st == "QM") query_max_path(x, y);
	}
	return 0;
}