日常复习模板系列。今日用时30min+30min=1h（后面的是调试）

记一些奇怪的trick：一直走top的时候判断dep[top[u]]和dep[top[v]]可以避免出现访问0节点。

# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

const int N = 30010, M = 60010;
int n, tot=0, head[N], next[M], to[M], we[N], DFN=0, son[N], sz[N], pos[N], dep[N], fa[N], top[N];

inline void add(int u, int v) {
	++tot; next[tot]=head[u]; head[u]=tot; to[tot]=v;
}

inline void dfs1(int x, int fat) {
	fa[x] = fat; dep[x] = dep[fat] + 1;
	sz[x] = 1; son[x] = -1;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fat) continue;
		dfs1(to[i], x);
		if(son[x] == -1 || sz[son[x]] < sz[to[i]]) son[x] = to[i];
		sz[x] = sz[x] + sz[to[i]];
	}
}

inline void dfs2(int x, int fa, int tp) {
	pos[x] = ++DFN; top[x] = tp;
	if(son[x] != -1) dfs2(son[x], x, tp);
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa || to[i] == son[x]) continue;
		dfs2(to[i], x, to[i]);
	}
}

typedef long long ll;
ll w[N<<2], lazy[N<<2], mx[N<<2];
  
inline void pushdown(int x, int l, int r) {
    if(lazy[x] == -1) return;
    int mid = l+r >> 1;
    w[x<<1] = lazy[x] * (mid - l + 1);
    w[x<<1|1] = lazy[x] * (r - (mid+1) + 1);
    mx[x<<1] = mx[x<<1] + lazy[x];
    mx[x<<1|1] = mx[x<<1|1] + lazy[x];
    lazy[x<<1] = lazy[x];
    lazy[x<<1|1] = lazy[x];
    lazy[x] = -1;
}
  
inline void change(int x, int l, int r, int L, int R, int delta) {
    if(L <= l && r <= R) {
        w[x] += delta*(r - l + 1);
        mx[x] = mx[x] + delta;
        lazy[x] = delta;
        return ;
    }
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) change(x<<1|1, mid+1, r, L, R, delta);
    else if(R <= mid) change(x<<1, l, mid, L, R, delta);
    else {
        change(x<<1, l, mid, L, mid, delta);
        change(x<<1|1, mid+1, r, mid+1, R, delta);
    }
    w[x] = w[x<<1] + w[x<<1|1];
    mx[x] = max(mx[x<<1], mx[x<<1|1]);
}
  
inline ll querysum(int x, int l, int r, int L, int R) {
    if(L <= l && r <= R) return w[x];
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) return querysum(x<<1|1, mid+1, r, L, R);
    else if(R <= mid) return querysum(x<<1, l, mid, L, R);
    else return querysum(x<<1, l, mid, L, mid) + querysum(x<<1|1, mid+1, r, mid+1, R);
}

inline ll querymax(int x, int l, int r, int L, int R) {
    if(L <= l && r <= R) return mx[x];
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) return querymax(x<<1|1, mid+1, r, L, R);
    else if(R <= mid) return querymax(x<<1, l, mid, L, R);
    else {
		ll ql = querymax(x<<1, l, mid, L, mid), qr = querymax(x<<1|1, mid+1, r, mid+1, R);
		return max(ql, qr);
	}
}

inline ll getmax(int u, int v) {
	ll ret = -66666, tu, tv;
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		tu = querymax(1, 1, n, pos[top[u]], pos[u]);
		ret = max(ret, tu);
		u = fa[top[u]];
	}
	if(dep[u] <= dep[v]) {
		tu = querymax(1, 1, n, pos[u], pos[v]);
	} else tu = querymax(1, 1, n, pos[v], pos[u]);
	ret = max(ret, tu);
	return ret;
}

inline ll getsum(int u, int v) {
	ll ret = 0, tu;
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		tu = querysum(1, 1, n, pos[top[u]], pos[u]);
		ret = ret + tu;
		u = fa[top[u]];
	}
	if(dep[u] <= dep[v]) {
		tu = querysum(1, 1, n, pos[u], pos[v]);
	} else tu = querysum(1, 1, n, pos[v], pos[u]);
	ret = ret + tu;
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i=1, u, v; i<n; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs1(1, 0);
	dfs2(1, 0, 1);
	for (int i=1; i<(n<<2); ++i) lazy[i] = -1;
	for (int i=1; i<=n; ++i) {
		scanf("%d", &we[i]);
		change(1, 1, n, pos[i], pos[i], we[i]);
	}
	int q;
	char opt[8];
	scanf("%d", &q);
	while(q--) {
		scanf("%s", opt);
		if(opt[1] == 'M') {
			int u, v;
			scanf("%d%d", &u, &v);
			// qmax
			printf("%lld\n", getmax(u, v));
		} else if(opt[1] == 'S') {
			// qsum
			int u, v;
			scanf("%d%d", &u, &v);
			printf("%lld\n", getsum(u, v));
		} else {
			// change
			int x, de;
			scanf("%d%d", &x, &de);
			change(1, 1, n, pos[x], pos[x], de-we[x]);
			we[x]=de;
		}
	}
	return 0;
}