记录编号	558200	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	fsdh	是否通过	通过
代码语言	C++	运行时间	1.313 s
提交时间	2020-12-13 21:46:43	内存使用	4.39 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define Debug puts ("Debug");
using namespace std;
const int MAXN = 3e4 + 5;
struct Edge {
	int next, to;
}edge[MAXN << 1];
int head[MAXN], cnt = 0;
struct Tree {
	int f, dep, size, son, top, seg;
}tree[MAXN];
struct Segment {
	int sum, maxn;
}t[MAXN << 2];
int n, w[MAXN], m, ansq, ansm;
int rev[MAXN];

template <typename T>
inline void read (T &x) {
	x = 0; int f = 1; char ch = getchar ();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar (); }
	while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch - '0'), ch = getchar ();
	x *= t; return ;
}

inline void add (int from, int to) {
	edge[++ cnt].next = head[from]; head[from] = cnt; edge[cnt].to = to;
	edge[++ cnt].next = head[to]; head[to] = cnt; edge[cnt].to = from;
	return ;
}

inline void dfs1 (int u, int fa) {
	tree[u].size = 1, tree[u].f = fa, tree[u].dep = tree[fa].dep + 1;
	for (int q = head[u]; ~q; q = edge[q].next) {
		int v = edge[q].to;
		if (v == fa) continue ;
		dfs1 (v, u);
		tree[u].size += tree[v].size;
		if (tree[v].size > tree[tree[u].son].size) tree[u].son = v;
	} return ; 
}

inline void dfs2 (int u, int fa) {
	if (tree[u].son) {
		tree[tree[u].son].seg = ++tree[0].seg, tree[tree[u].son].top = tree[u].top;
		rev[tree[0].seg] = tree[u].son, dfs2 (tree[u].son, u);
	}
	for (int q = head[u]; ~q; q = edge[q].next) {
		int v = edge[q].to;
		if (v == fa || v == tree[u].son) continue ;
		tree[v].seg = ++tree[0].seg, tree[v].top = v;
		rev[tree[0].seg] = v;
		dfs2 (v, u);
	} return ;
}

inline void pushup (int i) {
	t[i].sum = t[i << 1].sum + t[i << 1 | 1].sum;
	t[i].maxn = max (t[i << 1].maxn, t[i << 1 | 1].maxn); return ;
}

inline void build (int i, int l, int r) {
	if (l == r) { t[i].sum = t[i].maxn = w[rev[l]]; return ; }
	int mid = (l + r) >> 1;
	build (i << 1, l, mid); build (i << 1 | 1, mid + 1, r);
	pushup (i); return ;
}

inline void change (int i, int l, int r, int val, int x) {
	if (l > x || r < x) return ;
	if (l == r && l == x) { t[i].sum = t[i].maxn = val; return ; }
	int mid = (l + r) >> 1;
	if (x <= mid) change (i << 1, l, mid, val, x);
	else change (i << 1 | 1, mid + 1, r, val, x);
	pushup (i); return ;
}

inline void query_s (int i, int l, int r, int L, int R) {
	if (l >= L && r <= R) {
		ansq += t[i].sum; ansm = max (ansm, t[i].maxn);
		return ;
	}
	if (l > R || r < L) return ;
	int s = 0, mid = (l + r) >> 1;
	if (mid >= L) query_s (i << 1, l, mid, L, R);
	if (mid < R) query_s (i << 1 | 1, mid + 1, r, L, R);
	return ;
}

inline void ask (int x, int y) {
	int fx = tree[x].top, fy = tree[y].top;
	while (fx != fy) {
		if (tree[fx].dep < tree[fy].dep) swap (fx, fy), swap (x, y);
		query_s (1, 1, tree[0].seg, tree[fx].seg, tree[x].seg);
		x = tree[fx].f, fx = tree[x].top;
	}
	if (tree[x].dep < tree[y].dep) swap (x, y);
	query_s (1, 1, tree[0].seg, tree[y].seg, tree[x].seg);
	return ;
}

int main () {
	memset (head, -1, sizeof (head));
	freopen ("bzoj_1036.in", "r", stdin);
	freopen ("bzoj_1036.out", "w", stdout);
	scanf ("%d", &n);
	for (int q = 1, a, b; q < n; ++q) {
		scanf ("%d%d", &a, &b);
		add (a, b);
	}
	for (int q = 1; q <= n; ++q) scanf ("%d", &w[q]);
	dfs1 (1, 0); tree[0].seg = tree[1].seg = rev[1] = tree[1].top = 1;
	dfs2 (1, 0); build (1, 1, tree[0].seg);
	scanf ("%d", &m);
	int x, y; char op[11]; 
	while (m--) {
		scanf ("%s", op); scanf ("%d%d", &x, &y);
		if (op[0] == 'C') change (1, 1, tree[0].seg, y, tree[x].seg);
		else {
			ansm = -0x3f3f3f3f, ansq = 0;
			ask (x, y);
			if (op[1] == 'S') {
				printf ("%d\n", ansq);
			}
			else printf ("%d\n", ansm);
		}
	}
	return 0;
}