30pts玄学RE,vector写法动态开点

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'

const int N = 1e5 + 5;

int n, q, c[N], w[N], tt[N << 1];
int dfn[N], rnk[N], dep[N], son[N], fa[N], tp[N], sz[N], tot;
vector<int> G[N];

void dfs1(int u, int p) {
	dep[u] = dep[p] + 1;
	fa[u]= p;
	sz[u] = 1;
	for (int &v : G[u]) {
		if (v == p) continue;
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}

void dfs2(int u, int tpk) {
	dfn[u] = ++tot;
	rnk[tot] = u;
	tp[u] = tpk;
	if (son[u]) dfs2(son[u], tpk);
	for (int &v : G[u]) {
		if (v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}

struct node {
	int ls, rs;
	ll maxx, sum;
};
vector<node> sgt[N << 1];
int one = 1;

int ls(int now, int u) {return sgt[now][u].ls;}
int rs(int now, int u) {return sgt[now][u].rs;}

void push_up(int now, int u) {
	sgt[now][u].maxx = max(sgt[now][ls(now, u)].maxx, sgt[now][rs(now, u)].maxx);
	sgt[now][u].sum = sgt[now][ls(now, u)].sum + sgt[now][rs(now, u)].sum;
}

void update(int now, int &u, int beg, int en, int x) {
	if (!u) {
		u = ++tt[now];
		sgt[now].push_back({0, 0, 0, 0});
	}
	if (beg >= en) {
		sgt[now][u].maxx = sgt[now][u].sum = w[rnk[x]];
		return;
	}
	int mid = beg + en >> 1;
	if (x <= mid)
		update(now, sgt[now][u].ls, beg, mid, x);
	else
		update(now, sgt[now][u].rs, mid + 1, en, x);
//	cout << ls(now, u) << ' ' << rs(now, u)<< ' ' << sgt[now][ls(now, u)].sum << ' ' << sgt[now][rs(now, u)].sum << endl;
	push_up(now, u);
//	cout << now << ' ' << u << ' ' << beg  << ' ' << en << ' ' << x << ' ' << sgt[now][u].sum<< endl;
}

void del(int now, int u, int beg, int en, int x) {
	if (beg >= en) {
		sgt[now][u].maxx = sgt[now][u].sum = 0;
		return;
	}
	int mid = beg + en >> 1;
	if (x <= mid)
		del(now, ls(now, u), beg, mid, x);
	else
		del(now, rs(now, u), mid + 1, en, x);
	push_up(now, u);
}

ll qmax(int now, int u, int beg, int en, int l, int r) {
	if (beg >= l && en <= r)
	   return sgt[now][u].maxx;
	int mid = beg + en >> 1;
	if (r <= mid)
		return qmax(now, ls(now, u), beg, mid, l, r);
	else if (l > mid)
		return qmax(now, rs(now, u), mid + 1, en, l, r);
	else
		return max(qmax(now, ls(now, u), beg, mid, l, mid),
					qmax(now, rs(now, u), mid + 1, en, mid + 1, r));
}

ll qsum(int now, int u, int beg, int en, int l, int r) {
//	cout << now << ' ' << u << ' ' << beg  << ' ' << en << ' ' << l << ' ' << r << ' ' << sgt[now][u].sum << endl;
	if (beg >= l && en <= r)
	   return sgt[now][u].sum;
	int mid = beg + en >> 1;
	if (r <= mid)
		return qsum(now, ls(now, u), beg, mid, l, r);
	else if (l > mid)
		return qsum(now, rs(now, u), mid + 1, en, l, r);
	else
		return qsum(now, ls(now, u), beg, mid, l, mid) +
				qsum(now, rs(now, u), mid + 1, en, mid + 1, r);
}

ll Qmax(int now, int u, int v) {
	ll ans = 0;
	while (tp[u] != tp[v]) {
		if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
		ans = max(ans, qmax(now, one, 1, n, dfn[tp[u]], dfn[u]));
		u = fa[tp[u]];
	}
	if (dep[u] > dep[v]) swap(u, v);
	ans = max(ans, qmax(now, one, 1, n, dfn[u], dfn[v]));
	return ans;
}

ll Qsum(int now, int u, int v) {
	ll ans = 0;
	while (tp[u] != tp[v]) {
		if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
		ans += qsum(now, one, 1, n, dfn[tp[u]], dfn[u]);
		u = fa[tp[u]];
	}
//	cout << u << ' ' << v << ' ' << ans << endl;
	if (dep[u] > dep[v]) swap(u, v);
	ans += qsum(now, one, 1, n, dfn[u], dfn[v]);
	return ans;
}

int main() {
	IOS;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> c[i];
	}
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 1);
	dfs2(1, 1);
	for (int i = 1; i <= n; i++) {
		if (!tt[c[i]])
			sgt[c[i]].push_back({0, 0, 0, 0}), sgt[c[i]].push_back({0, 0, 0, 0}), tt[c[i]] = 1;
//		cout << "AC " << tt[c[i]] << ' ' << c[i] << ' ' << w[i] << endl;
		update(c[i], one, 1, n, dfn[i]);
	}
//	cout << qsum(3, 1, 1, n, 1, n) << endl;
	while (q--) {
		string op;
		int x, y;
		cin >> op >> x >> y;
		if (op == "CC") {
			del(c[x], one, 1, n, dfn[x]);
			c[x] = y;
			if (!tt[c[x]])
				sgt[c[x]].push_back({0, 0, 0, 0}), sgt[c[x]].push_back({0, 0, 0, 0}), tt[c[x]] = 1;
			update(c[x], one, 1, n, dfn[x]);
		} else if (op == "CW") {
			w[x] = y;
			update(c[x], one, 1, n, dfn[x]);
		} else if (op == "QS") {
			cout << Qsum(c[x], x, y) << endl;
		} else {
			cout << Qmax(c[x], x, y) << endl;
		}
	}
	return 0;
}