树链剖分：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>using namespace std;#define rep(i, l, r) for (int i = l; i <= r; i++)#define REP(i, l, r) for (int i = l; i >= r; i–)#define INF 2147483647#define MAXN 1000010int n, N = -1, M = 0, m, first[MAXN], next[MAXN], NUM[MAXN], root, T_T, c[MAXN];int dep[MAXN], siz[MAXN], son[MAXN], fa[MAXN], top[MAXN], w[MAXN];struct tlist {int x, y;} a[MAXN];bool vis[MAXN];struct Tree {int l, r, lc, rc, sum, max;} tree[MAXN];inline void swap(int &a, int &b) {int t = a; a = b; b = t;}inline void add(int x, int y) {a[++N].x = x, a[N].y = y, next[N] = first[x], first[x] = N;}inline void dfs(int x, int d) {dep[x] = d;siz[x] = 1;vis[x] = 1;int maxsize = 0, k = 0;for (int i = first[x]; ~i; i = next[i])if (!vis[a[i].y]) {vis[a[i].y] = 1;dfs(a[i].y, d+1);siz[x] += siz[a[i].y];if (siz[a[i].y] > maxsize) maxsize = siz[a[i].y], k = a[i].y;}son[x] = k;}inline void DFS(int x, int T) {top[x] = T;vis[x] = 1;if (son[x]) w[son[x]] = ++M, NUM[M] = son[x], DFS(son[x], T);for (int i = first[x]; ~i; i = next[i])if (!vis[a[i].y]) {w[a[i].y] = ++M;NUM[M] = a[i].y;DFS(a[i].y, a[i].y);}}inline void build_tree(int i, int L, int R) {tree[i].l = L, tree[i].r = R;if (L == R) {tree[i].sum = tree[i].max = c[NUM[L]]; return;}build_tree(tree[i].lc = ++m, L, (L+R) >> 1);build_tree(tree[i].rc = ++m, ((L+R) >> 1) + 1, R);tree[i].max = max(tree[tree[i].lc].max, tree[tree[i].rc].max);tree[i].sum = tree[tree[i].lc].sum + tree[tree[i].rc].sum;}inline void modify(int i, int x, int cx) {int L = tree[i].l, R = tree[i].r;if (x < L || x > R) return;if (L == R) {tree[i].sum = tree[i].max = cx; return;}modify(tree[i].lc, x, cx);modify(tree[i].rc, x, cx);tree[i].max = max(tree[tree[i].lc].max, tree[tree[i].rc].max);tree[i].sum = tree[tree[i].lc].sum + tree[tree[i].rc].sum;}inline int query_max(int i, int ql, int qr) {int L = tree[i].l, R = tree[i].r;if (qr < L || ql > R) return -INF;if (L >= ql && R <= qr) return tree[i].max;return max(query_max(tree[i].lc, ql, qr), query_max(tree[i].rc, ql, qr));}inline int query_sum(int i, int ql, int qr) {int L = tree[i].l, R = tree[i].r;if (qr < L || ql > R) return 0;if (L >= ql && R <= qr) return tree[i].sum;return query_sum(tree[i].lc, ql, qr) + query_sum(tree[i].rc, ql, qr);}int main() {cin >> n;memset(first, -1, sizeof(first));memset(next, -1, sizeof(next));memset(fa, 0, sizeof(fa));rep(i, 1, n-1) {int tx, ty;scanf("%d%d", &tx, &ty);fa[ty] = tx;if (!fa[tx]) root = tx;add(tx, ty), add(ty, tx);}rep(i, 1, n) scanf("%d", &c[i]);memset(vis, 0, sizeof(vis));dfs(root, 1);memset(vis, 0, sizeof(vis));w[root] = ++M, NUM[M] = root;DFS(root, root);build_tree(m = 1, 1, n);cin >> T_T;while (T_T–) {char ch[MAXN];int tx, ty;scanf("%s", ch);scanf("%d%d", &tx, &ty);if (ch[0] == 'C') modify(1, w[tx], ty);if (ch[1] == 'M') {int f1, f2, maxans = -INF;while ((f1 = top[tx]) != (f2 = top[ty])) {if (dep[f1] < dep[f2]) swap(f1, f2), swap(tx, ty);maxans = max(maxans, query_max(1, w[f1], w[tx]));tx = fa[f1];}if (dep[tx] < dep[ty]) swap(tx, ty);maxans = max(maxans, query_max(1, w[ty], w[tx]));cout << maxans << endl;}if (ch[1] == 'S') {int f1, f2, sumans = 0;while ((f1 = top[tx]) != (f2 = top[ty])) {if (dep[f1] < dep[f2]) swap(f1, f2), swap(tx, ty);sumans += query_sum(1, w[f1], w[tx]);tx = fa[f1];}if (dep[tx] < dep[ty]) swap(tx, ty);sumans += query_sum(1, w[ty], w[tx]);cout << sumans << endl;}}return 0;}
，旁观者的姓名永远爬不到比赛的计分板上。
