记录

#include<iostream>
using namespace std;
const int N = 30005;
struct Edge { int v, next; };
Edge e[4*N];
int head[N], tot = 0;
inline void insert(int u, int v)
{
	tot++;
	e[tot] = { v, head[u] };
	head[u] = tot;
}
int num[N];
int fa[N], dep[N], son[N], sz[N];
int top[N], cnt = 0, seg[N], rev[N];
void dfs_1(int p)
{
	sz[p] = 1;
	int m = -1;
	for(int i=head[p];i;i=e[i].next)
	{
		int to = e[i].v;
		if(to != fa[p])
		{
			fa[to] = p;
			dep[to] = dep[p]+1;
			dfs_1(to);
			sz[p] += to;
			if(sz[to] >= m)
			{ m = sz[to]; son[p] = to; }
		}
	}
}
void dfs_2(int p, int t)
{
	top[p] = t;
	cnt++;
	seg[p] = cnt;
	rev[cnt] = p;
	if(son[p]) dfs_2(son[p], t);
	for(int i=head[p];i;i=e[i].next)
		if(e[i].v != fa[p] && e[i].v != son[p])
			dfs_2(e[i].v, e[i].v);
}
struct seg_tree { int l, r, Sum, Max; };
seg_tree st[4*N];
void bt(int p, int l, int r)
{
	st[p] = { l, r, 0, -100000000 };
	if(l == r)
	{
		st[p].Sum = st[p].Max = num[rev[l]];
		return ;
	}
	int mid = (l + r) / 2;
	bt(p*2, l, mid);
	bt(p*2+1, mid+1, r);
	st[p].Sum = st[p*2].Sum + st[p*2+1].Sum;
	st[p].Max = max(st[p*2].Max, st[p*2+1].Max);
}
void seg_upd(int p, int u, int t)
{
	if(st[p].l == st[p].r)
	{
		st[p].Sum = st[p].Max = t;
		return ;
	}
	int mid = (st[p].l + st[p].r) / 2;
	if(u <= mid) seg_upd(p*2, u, t);
	else seg_upd(p*2+1, u, t);
	st[p].Sum = st[p*2].Sum + st[p*2+1].Sum;
	st[p].Max = max(st[p*2].Max, st[p*2+1].Max);
}
inline void upd(int u, int t) { seg_upd(1, seg[u], t); }
int seg_max(int p, int l, int r)
{
	if(l <= st[p].l && r >= st[p].r) { return st[p].Max; }
	int mid = (st[p].l + st[p].r) / 2;
	int ans = -100000000;
	if(l <= mid) ans = seg_max(p*2, l, r);
	if(r >= mid+1) ans = max(ans, seg_max(p*2+1, l, r));
	return ans;
}
int seg_sum(int p, int l, int r)
{
	if(l <= st[p].l && r >= st[p].r) { return st[p].Sum; }
	int mid = (st[p].l + st[p].r) / 2;
	int ans = 0;
	if(l <= mid) ans += seg_sum(p*2, l, r);
	if(r >= mid+1) ans += seg_sum(p*2+1, l, r);
	return ans;
}
inline int Max(int u, int v)
{
	int ans = -100000000;
	while(top[u] != top[v])
	{
		if(dep[top[v]] < dep[top[u]]) swap(u, v);
		ans = max(ans, seg_max(1, seg[top[v]], seg[v]));
		v = fa[top[v]];
	}
	if(dep[u] > dep[v]) swap(u, v);
	ans = max(ans, seg_max(1, seg[u], seg[v]));
	return ans;
}
inline int Sum(int u, int v)
{
	int ans = 0;
	while(top[u] != top[v])
	{
		if(dep[top[v]] < dep[top[u]]) swap(u, v);
		ans += seg_sum(1, seg[top[v]], seg[v]);
		v = fa[top[v]];
	}
	if(dep[u] > dep[v]) swap(u, v);
	ans += seg_sum(1, seg[u], seg[v]);
	return ans;
}
int main()
{
	ios::sync_with_stdio(false); 
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for(int i=1;i<=n-1;i++)
	{
		int a, b;
		cin >> a >> b;
		insert(a, b);
		insert(b, a);
	}
	for(int i=1;i<=n;i++)
		cin >> num[i];
	dfs_1(1);
	dfs_2(1, 1);
	bt(1, 1, n);
	int q;
	cin >> q;
	for(int i=1;i<=q;i++)
	{
		char op[10];
		int x, y;
		cin >> op >> x >> y;
		if(op[1] == 'H') upd(x, y);
		else if(op[1] == 'M') cout << Max(x, y) << '\n';
		else cout << Sum(x, y) << '\n';
	}
	return 0;
}