0 pts

样例过。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
const int N = 3e4 + 4;
int n, w[N], q;
vector <int> G[N];
int son[N], siz[N], dep[N], fa[N], tp[N], dfn[N], rnk[N], cnt;
string s;
int x, y, ww;
struct Segment_Tree {
	int sum = 0, maxx = 0;
} tr[N << 3];
void predfs(int u, int fa_) {
	son[u] = -1;
	siz[u] = 1;
	for (int v : G[u]) {
		if (v == fa_) continue;
		dep[v] = dep[u] + 1;
		fa[v] = u;
		predfs(v, u);
		siz[u] += siz[v];
		if (son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
	}
	return ;
}
void dfs(int u, int t) {
	tp[u] = t;
	dfn[u] = ++cnt;
	rnk[cnt] = u;
	if (son[u] == -1) return ;
	dfs(son[u], t);
	for (int v : G[u]) {
		if (v == fa[u] || v == son[u]) continue;
		dfs(v, v);
	}
	return ;
}
void push_up(int id) {
	tr[id].sum = tr[id * 2].sum + tr[id * 2 + 1].sum;
	tr[id].maxx = max(tr[id * 2].maxx, tr[id * 2 + 1].maxx);
	return ;
}
void Build(int id, int l, int r) {
	if (l == r) {
		tr[id].sum = w[l], tr[id].maxx = w[l];
		return ;
	}
	int mid = (l + r) >> 1;
	Build(id * 2, l, mid);
	Build(id * 2 + 1, mid + 1, r);
	push_up(id);
	return ;
}
void upd(int id, int l, int r, int x, int val) {
	if (l == r) {
		tr[id].sum = val, tr[id].maxx = val;
		return ;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) upd(id * 2, l, mid, x, val);
	else upd(id * 2 + 1, mid + 1, r, x, val);
	push_up(id);
	return ;
}
int query_max(int id, int l, int r, int x, int y) {
	if (l == r) {
		return tr[id].maxx;
	}
	int mid = (l + r) >> 1, res = 0;
	if (x <= mid) res = max(res, query_max(id * 2, l, mid, x, y));
	if (y > mid) res = max(res, query_max(id * 2 + 1, mid + 1, r, x, y));
	return res;
}
int query_sum(int id, int l, int r, int x, int y) {
	if (l == r) return tr[id].sum;
	int mid = (l + r) >> 1, res = 0;
	if (x <= mid) res += query_sum(id * 2, l, mid, x, y);
	if (y > mid) res += query_sum(id * 2 + 1, mid + 1, r, x, y);
	return res;
}
int qmax(int x, int y) {
	int res = 0;
	while (tp[x] != tp[y]) {
		if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
		res = max(res, query_max(1, 1, n, dfn[tp[x]], dfn[x]));
		x = fa[tp[x]];
	}
	if (dep[x] < dep[y]) swap(x, y);
	res = max(res, query_max(1, 1, n, dfn[y], dfn[x]));
	return res;
}
int qsum(int x, int y) {
	int res = 0;
	while (tp[x] != tp[y]) {
		if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
		res += query_sum(1, 1, n, dfn[tp[x]], dfn[x]);
		x = fa[tp[x]];
	}
	if (dep[x] < dep[y]) swap(x, y);
	res += query_sum(1, 1, n, dfn[y], dfn[x]);
	return res;
}
int main(void) {
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1, a, b; i < n; ++i) {
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}	
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
	}
	predfs(1, 0);
	dfs(1, 1);
	Build(1, 1, n);
	cin >> q;
	while (q--) {
		cin >> s;
		if (s == "CHANGE") {
			cin >> x >> ww;
			upd(1, 1, n, dfn[x], ww);
		}
		else if (s == "QMAX") {
			cin >> x >> y;
			cout << qmax(x, y) << '\n';
		}
		else {
			cin >> x >> y;
			cout << qsum(x, y) << '\n';
		}
	}
    return 0;
}