AC on #5 #6 #9

#include<bits/stdc++.h>
using namespace std;
int siz[400005];//子树大小
int hson[400005];//重儿子
long long a[400005];
int deep[400005];
int rak[400005];//这个dfn值对应的编号
int dfn[400005];//这个点的dfn值
int top[400005];//这点所在的链的链顶
int vis[400005];
long long seg[400005];//线段树
long long maxx[400005];
int fa[400005];
vector<int> g[30005];
int n, m;
int dfs(int pos) {
	hson[pos] = 0;
	siz[pos] = 1;
	for (auto x : g[pos]) {
		if (!deep[x]) {
			fa[x] = pos;
			deep[x] = deep[pos] + 1;
			siz[pos] += dfs(x);
			if (siz[x] > siz[hson[pos]]) {
				hson[pos] = x;
			}
		}
	}
	return siz[pos];
}
int cnt;
void dfs2(int t, int pos) {
	top[pos] = t;
	dfn[++cnt] = pos;
	rak[pos] = cnt;
	if (g[pos].size() == 0) return;//叶子节点没有儿子，直接返回
	if (hson[pos] != 0) {
		vis[hson[pos]] = 1;
		dfs2(t, hson[pos]);
	}
	for (auto x : g[pos]) {
		if (!vis[x]) {
			vis[x] = 1;
			dfs2(x, x);
		}
	}
}
void upd(int x) {
	seg[x] = seg[x * 2] + seg[x * 2 + 1];
	maxx[x] = max(maxx[x * 2], maxx[x * 2 + 1]);
}
void bt(int l, int r, int pos) {
	if (l == r) {
		seg[pos] = a[dfn[l]];
		maxx[pos] = a[dfn[l]];
		return;
	}
	int mid = (l + r) >> 1;
	bt(l, mid, pos * 2);
	bt(mid + 1, r, pos * 2 + 1);
	upd(pos);
}
void modi(int x, int L, int R, int pos, long long val) {
	if (L == R) {
		seg[pos] = val;
		maxx[pos] = val;
		return;
	}
	int mid = (L + R) >> 1;
	if (x > mid) modi(x, mid + 1, R, pos * 2 + 1, val);
	else modi(x, L, mid, pos * 2, val);
	upd(pos);
}
long long qsum(int l, int r, int L, int R, int pos) {
	if (l <= L && r >= R) {
		return seg[pos];
	} else if (l > R || r < L) return 0;
	int mid = (L + R) >> 1;
	return qsum(l, r, L, mid, pos * 2) + qsum(l, r, mid + 1, R, pos * 2 + 1);
}
long long maxsum(int l, int r, int L, int R, int pos) {
	if (l <= L && r >= R) {
		return maxx[pos];
	} else if (l > R || r < L) return LLONG_MIN; // 极小值
	int mid = (L + R) >> 1;
	return max(maxsum(l, r, L, mid, pos * 2), maxsum(l, r, mid + 1, R, pos * 2 + 1));
}
long long squel(int x, int y) {
	long long ans = 0;
	int fx = top[x], fy = top[y];
	while (fx != fy) {
		if (deep[fx] >= deep[fy]) {//fx深就把x跳到链顶
			ans += qsum(dfn[fx], dfn[x], 1, n, 1);
			x = fa[fx];
		} else {//不然跳y
			ans += qsum(dfn[fy], dfn[y], 1, n, 1);
			y = fa[fy];
		}
		fx = top[x];
		fy = top[y];
	}
	if (deep[x] >= deep[y]) {
		ans += qsum(dfn[y], dfn[x], 1, n, 1);
	} else {
		ans += qsum(dfn[x], dfn[y], 1, n, 1);
	}
	return ans;
}
long long mquel(int x, int y) {
	long long ans = LLONG_MIN;
	int fx = top[x], fy = top[y];
	while (fx != fy) {
		if (deep[fx] >= deep[fy]) {//fx深就把x跳到链顶
			ans = max(maxsum(dfn[fx], dfn[x], 1, n, 1), ans);
			x = fa[fx];
		} else {
			ans = max(maxsum(dfn[fy], dfn[y], 1, n, 1), ans);
			y = fa[fy];
		}
		fx = top[x];
		fy = top[y];
	}
	if (deep[x] >= deep[y]) {
		ans = max(maxsum(dfn[y], dfn[x], 1, n, 1), ans);
	} else {
		ans = max(maxsum(dfn[x], dfn[y], 1, n, 1), ans);
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> m;
	deep[1] = 1;
	fa[1] = 1;
	dfs(1);
	vis[1] = 1;
	dfs2(1, 1);
	bt(1, cnt, 1);
	for (int i = 1; i <= m; i++) {
		string op;
		int x, y;
		cin >> op >> x >> y;
		if (op == "QMAX") {
			cout << mquel(x, y) << endl;
		} else if (op == "QSUM") {
			cout << squel(x, y) << endl;
		} else if (op == "CHANGE") {
			modi(dfn[x], 1, cnt, 1, y);
		}
	}
}