rt,样例过了然而抱灵了/kk

然后这题还不给数据，代码感觉非常对不知道哪里写挂了……有神仙看看吗/kel

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define maxn 10000005
using namespace std;

inline int read()
{
    int x = 0, w = 1;char ch = getchar();
    while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
    while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();
    return x * w;
}

struct segment { ll max, sum; } tree[maxn << 2];
struct node { ll to, nxt; } edge[maxn];
ll n, q, dfs_block, tot, res;
ll head[maxn], val[maxn], a[maxn];
ll son[maxn], dfn[maxn], fa[maxn], dep[maxn], siz[maxn], top[maxn];

inline ll lson(ll x) { return x << 1; }
inline ll rson(ll x) { return x << 1 | 1; }
inline void push_up(ll x)
{
	tree[x].sum = tree[lson(x)].sum + tree[rson(x)].sum;
	tree[x].max = max(tree[lson(x)].max, tree[rson(x)].max);
}
inline void add(int u, int v)
{
	edge[++tot].nxt = head[u];
	edge[tot].to = v;
	head[u] = tot;
}
inline void addedge(int u, int v)
{
	add(u, v), add(v, u);
}

void build(ll x, ll l, ll r)
{
	if (l == r)
	{
		tree[x].sum = tree[x].max = a[l];
		return;
	}
	ll mid = (l + r) >> 1;
	build(lson(x), l, mid);
	build(rson(x), mid + 1, r);
	push_up(x);
}

void modify(ll x, ll l, ll r, ll to, ll k)
{
	if (l == r)
	{
		tree[x].sum = tree[x].max = k;
		return;	
	}
	ll mid = (l + r) >> 1;
	if (to <= mid) modify(lson(x), l, mid, to, k);
	if (to > mid) modify(rson(x), mid + 1, r, to, k);
	push_up(x);
}

ll query_max(ll x, ll l, ll r, ll L, ll R)
{
	if (l >= L && r <= R) return tree[x].max;
	ll mid = (l + r) >> 1, ans = -1;
	if (mid >= L) ans = max(ans, query_max(lson(x), l, mid, L, R));
	if (mid < R) ans = max(ans, query_max(rson(x), mid + 1, r, L, R));
	return ans;
}

ll query_sum(ll x, ll l, ll r, ll L, ll R)
{
	if (l >= L && r <= R) return tree[x].sum;
	ll mid = (l + r) >> 1, res = 0;
	if (mid >= L) res += query_sum(lson(x), l, mid, L, R);
	if (mid < R) res += query_sum(rson(x), mid + 1, r, L, R);
	return res;
}

void dfs1(int u, int fath)
{
	siz[u] = 1, dep[u] = dep[fath] + 1;
	fa[u] = fath, son[u] = 0;
	for (int i = head[u];i;i = edge[i].nxt)
	{
		int v = edge[i].to;
		if (v == fath) continue;
		dfs1(v, u);siz[u] += siz[v];
		if (siz[v] > siz[son[u]])
			son[u] = v;
	}
}

void dfs2(int u)
{
	dfn[u] = ++dfs_block, a[dfs_block] = val[u];
	if (u == son[fa[u]]) top[u] = top[fa[u]];
	else top[u] = u;
	if (son[u]) dfs2(son[u]);
	for (int i = head[u];i;i = edge[i].nxt)
	{
		int v = edge[i].to;
		if (v != fa[u] && v != son[u]) dfs2(v);
	}
}

ll query_max_chain(int x, int y)
{
	ll res = -1;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		res = max(res, query_max(1, 1, n, dfn[top[x]], dfn[x]));
		x = fa[top[x]];
	}
	if (dep[x] < dep[y]) swap(x, y);
	res = max(res, query_max(1, 1, n, dfn[y], dfn[x]));
	return res;
}

ll query_sum_chain(int x, int y)
{
	ll res = 0;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		res += query_sum(1, 1, n, dfn[top[x]], dfn[x]);
		x = fa[top[x]];
	}
	if (dep[x] < dep[y]) swap(x, y);
	res += query_sum(1, 1, n, dfn[y], dfn[x]);
	return res;
}

int main(void)
{
	n = read();
	for (int i = 1;i < n;i++)
	{
		int u = read(), v = read();
		addedge(u, v);
	}
	for (int i = 1;i <= n;i++)
		val[i] = read();
	dfs1(1, 0), dfs2(1), build(1, 1, n);
	q = read();
	while (q--)
	{
		string opt;
		cin >> opt;
		if (opt[1] == 'H')
		{
			int u = read(), t = read();
			modify(1, 1, n, u, t);
		}
		else if (opt[1] == 'M')
		{
			int u = read(), v = read();
			printf("%lld\n", query_max_chain(u, v));
		}
		else if (opt[1] == 'S')
		{
			int u = read(), v = read();
			printf("%lld\n", query_sum_chain(u, v));
		}
	}
	return 0;
}