这里是代码，30ac70tle，写的是树剖，不会LCT tle的全都是1.20s，开O2实测无果，求助

#include <iostream>
#include <stdio.h>
#define maxn 30005
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
#define inf 0x3f3f3f3f
using namespace std;
int n, m;
int a[maxn];
struct edge {
	int to, nxt;
} e[maxn << 1];
int p[maxn], eid = 0;
void addedge (int u, int v) {
	e[++eid] = (edge){v, p[u]}, p[u] = eid;
	e[++eid] = (edge){u, p[v]}, p[v] = eid;
}
int f[maxn], siz[maxn], son[maxn], d[maxn], top[maxn], id[maxn], rk[maxn];
void dfs (int u, int fa) {
	siz[u] = 1;
	for (int i = p[u]; i; i = e[i].nxt) {
		int to = e[i].to;
		if (to == fa) continue;
		f[to] = u, d[to] = d[u] + 1;
		dfs (to, u);
		siz[u] += siz[to];
		if (siz[to] > siz[son[u]]) son[u] = to;
	}
	return ;
}
int cnt = 0;
void dfs2 (int u, int fa, int tp) {
	top[u] = tp, id[u] = ++cnt, rk[cnt] = u;
	if (!son[u]) return ;
	dfs2 (son[u], u, tp);
	for (int i = p[u]; i; i = e[i].nxt) {
		int to = e[i].to;
		if (to == son[u] || to == fa) continue;
		dfs2 (to, u, to);
	}
	return ;
}
int sum[maxn << 2], maxx[maxn << 2];
void pushup (int rt) {
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
	maxx[rt] = max (maxx[rt<<1], maxx[rt<<1|1]);
}
void build (int l, int r, int rt) {
	if (l == r) {
		sum[rt] = maxx[rt] = a[rk[l]];
		return ;
	}
	int mid = l + r >> 1;
	build (ls), build (rs);
	pushup (rt); 
}
void update (int l, int r, int rt, int x, int t) {
	if (l == r) {
		sum[rt] = t;
		maxx[rt] = t;
		return ;
	}
	int mid = l + r >> 1;
	if (x <= mid) update (ls, x, t);
	else update (rs, x, t);
	pushup (rt);
}
int querysum (int l, int r, int rt, int L, int R) {
	if (l == r) {
		return sum[rt];
	}
	int mid = l + r >> 1, res = 0;
	if (mid >= L) res += querysum (ls, L, R);
	if (mid < R) res += querysum (rs, L, R);
	return res;
} 
int queryssum (int u, int v) {
	int res = 0;
	while (top[u] != top[v]) {
		if (d[top[u]] < d[top[v]]) swap (u, v);
		res += querysum (1, n, 1, id[top[u]], id[u]);
		u = f[top[u]];
	}
	if (id[u] > id[v]) swap (u, v);
	res += querysum (1, n, 1, id[u], id[v]);
	return res;
}
int querymax (int l, int r, int rt, int L, int R) {
	if (l == r) {
		return maxx[rt];
	}
	int mid = l + r >> 1, res = -inf;
	if (mid >= L) res = max (res, querymax (ls, L, R));
	if (mid < R) res = max (res, querymax (rs, L, R));
	return res;
}
int querysmax (int u, int v) {
	int res = -inf;
	while (top[u] != top[v]) {
		if (d[top[u]] < d[top[v]]) swap (u, v);
		res = max (res, querymax (1, n, 1, id[top[u]], id[u]));
		u = f[top[u]];
	}
	if (id[u] > id[v]) swap (u, v);
	res = max (res, querymax (1, n, 1, id[u], id[v]));
	return res;
}
int main () {
	scanf ("%d", &n);
	for (int i = 1, u, v; i < n; i++) {
		scanf ("%d %d", &u, &v);
		addedge (u, v);
	}
	for (int i = 1; i <= n; i++) scanf ("%d", a+i);
	dfs (1, 0);
	dfs2 (1, 0, 1);
	build (1, n, 1);
	scanf ("%d", &m);
	char op[10]; int u, v;
	while (m--) {
		scanf ("%s %d %d", op, &u, &v);
		if (op[0] == 'C') {
			update (1, n, 1, id[u], v);
		} else if (op[1] == 'M') {
			printf ("%d\n", querysmax(u, v));
		} else if (op[1] == 'S') {
			printf ("%d\n", queryssum(u, v));
		}
	}
	return 0;
}