放 LOJ 上又 WA 又 T。

#include <iostream>
#include <vector>
#define int long long
using namespace std;
vector<int> a[1000005]; int f[1000005], dep[1000005], siz[1000005], Cubic[1000005], vis[1000005], top[1000005], qwq[1000005], qaq[1000005], hypercubic[100005][105], w[100005], c[100005], TLEWA[100005][105], cnt=0, n, bl=2000;
void dfs1(int x, int fa) {
f[x] = fa; dep[x] = dep[fa] + 1; siz[x] = 1;
for (int i: a[x]) if (i != fa) dfs1(i, x), siz[Cubic[x]] < siz[i] && (Cubic[x] = i), siz[x] += siz[i];
}
void dfs2(int x, int fa) {vis[x] = ++cnt;
top[x] = Cubic[fa] == x ? top[fa] : x; if (Cubic[x]) dfs2(Cubic[x], x); for (int i: a[x]) if (i != fa && i != Cubic[x]) dfs2(i, x);
}
void modify1(int x, int v) {
hypercubic[qwq[x]][(x-1)/bl+1] -= qaq[x]; TLEWA[qwq[x]][(x-1)/bl+1] = 0;
for (int i=(x-1)/bl*bl+1; i <= n && (i-1)/bl == (x-1)/bl; i++) if (qwq[i] == qwq[x]) TLEWA[qwq[x]][(x-1)/bl+1] = max(TLEWA[qwq[x]][(x-1)/bl+1], qaq[i]);
qwq[x] = v; hypercubic[v][(x-1)/bl+1] += qaq[x]; TLEWA[v][(x-1)/bl+1] = max(qaq[x], TLEWA[v][(x-1)/bl+1]);
}
void modify2(int x, int v) {
hypercubic[qwq[x]][(x-1)/bl+1] -= qaq[x]; qaq[x] = v; hypercubic[qwq[x]][(x-1)/bl+1] += qaq[x]; TLEWA[qwq[x]][(x-1)/bl+1] = 0;
for (int i=(x-1)/bl*bl+1; i <= n && (i-1)/bl == (x-1)/bl; i++) if (qwq[i] == qwq[x]) TLEWA[qwq[x]][(x-1)/bl+1] = max(TLEWA[qwq[x]][(x-1)/bl+1], qaq[i]);
}
int querys(int x, int y, int c) {int summ = 0;
for (int i=(x-1)/bl+2; i<=(y-1)/bl; i++) summ += hypercubic[c][i]; for (int i=x; i<=y && (x-1)/bl == (i-1)/bl; i++) if (qwq[i] == c) summ += qaq[i]; for (int i=y; i>=x && (y-1)/bl == (i-1)/bl && (x-1)/bl != (y-1)/bl; i--) if (qwq[i] == c) summ += qaq[i]; return summ;
}
int querym(int x, int y, int c) {int maxx = 0;
for (int i=(x-1)/bl+2; i<=(y-1)/bl; i++) maxx = max(maxx, TLEWA[c][i]); for (int i=x; i<=y && (x-1)/bl == (i-1)/bl; i++) if (qwq[i] == c) maxx = max(maxx, qaq[i]); for (int i=y; i>=x && (y-1)/bl == (i-1)/bl && (x-1)/bl != (y-1)/bl; i--) if (qwq[i] == c) maxx = max(maxx, qaq[i]); return maxx;
}
int querypm(int x, int y) {
int maxx=0, c=qwq[vis[x]]; while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
maxx = max(maxx, querym(vis[top[x]], vis[x], c)); x = f[top[x]];
} return max(maxx, querym(dep[x] < dep[y] ? vis[x] : vis[y], dep[x] > dep[y] ? vis[x] : vis[y], c));
}
int queryps(int x, int y) {
int summ=0, c=qwq[vis[x]]; while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
summ += querys(vis[top[x]], vis[x], c); x = f[top[x]];
} return summ + querys(dep[x] < dep[y] ? vis[x] : vis[y], dep[x] > dep[y] ? vis[x] : vis[y], c);
}
signed main() {
int u, v, x, q; string s; cin >> n >> q; for (int i=1; i<=n; i++) cin >> w[i] >> c[i]; for (int i=1; i<n; i++) cin >> u >> v, a[u].push_back(v), a[v].push_back(u); dfs1(1, 0); dfs2(1, 0); for (int i=1; i<=n; i++) modify1(vis[i], c[i]), modify2(vis[i], w[i]); while (q--) {
cin >> s >> u >> v; if (s == "CC") modify1(vis[u], v); else if (s == "CW") modify2(vis[u], v); else if (s == "QS") cout << queryps(u, v) << endl; else cout << querypm(u, v) << endl;
}
}