此题为树链剖分的裸题。 代码如下，使用常用的轻重链剖分。

/**************************************************************	Problem: 1036	User: Evensgn	Language: C++	Result: Accepted	Time:2468 ms	Memory:5772 kb****************************************************************/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <cstdlib>using namespace std;const int MaxE = 30000 + 5, MaxN = 30000 + 5;int n, q, topH, W[MaxN], f[MaxN], dep[MaxN], top[MaxN], son[MaxN], h[MaxN], size[MaxN], A[MaxN];int Ans;struct treeNode{	int sum, max;} T[MaxN * 4];struct edge {	int u, v;	edge *next;} E[MaxE * 2], *P = E, *point[MaxN];inline void addedge(int x, int y){	++P; P -> u = x; P -> v = y; P -> next = point[x]; point[x] = P;}int DFS_1(int now, int depth, int fa){	f[now] = fa;	dep[now] = depth;	int sonSize, maxSonSize = 0;	size[now] = 1;	for (edge *j = point[now]; j; j = j -> next)	{		if (j -> v != f[now])		{			sonSize = DFS_1(j -> v, depth + 1, now);			size[now] += sonSize;			if (maxSonSize < sonSize) 			{				son[now] = j -> v;				maxSonSize = sonSize;			}		}	}	return size[now];}void DFS_2(int now){	if (now != son[f[now]]) top[now] = now;	else top[now] = top[f[now]];	h[now] = ++topH;	A[h[now]] = W[now];	if (son[now]) DFS_2(son[now]);	for (edge *j = point[now]; j; j = j -> next)		if (j -> v != son[now] && j -> v != f[now]) DFS_2(j -> v);}int max(int a, int b){	if (a > b) return a;	return b;}void update(int x){	T[x].sum = T[x * 2].sum + T[x * 2 + 1].sum;	T[x].max = max(T[x * 2].max, T[x * 2 + 1].max);}void buildTree(int x, int s, int t){	if (s == t)	{		T[x].sum = A[s];		T[x].max = A[s];		return;	}	int m = (s + t) >> 1;	buildTree(x * 2, s, m);	buildTree(x * 2 + 1, m + 1, t);	update(x);}void change(int x, int s, int t, int loc, int num){	if (s == t)	{		T[x].sum = num;		T[x].max = num;		return;	}	int m = (s + t) >> 1;	if (loc <= m) change(x * 2, s, m, loc, num);	else change(x * 2 + 1, m + 1, t, loc, num);	update(x);}int getMax(int x, int s, int t, int l, int r){	if (l <= s && r >= t)		return T[x].max;	int m = (s + t) >> 1, ans = -999999999;	if (l <= m) ans = max(ans, getMax(x * 2, s, m, l, r));	if (r >= m + 1) ans = max(ans, getMax(x * 2 + 1, m + 1, t, l, r));	return ans;}int getSum(int x, int s, int t, int l, int r){	if (l <= s && r >= t)		return T[x].sum;	int m = (s + t) >> 1, ans = 0;	if (l <= m) ans += getSum(x * 2, s, m, l, r);	if (r >= m + 1) ans += getSum(x * 2 + 1, m + 1, t, l, r);	return ans;}void queryMax(int s, int t){	int f1, f2;	f1 = 0; f2 = 1;	while (f1 != f2)	{		f1 = top[s];		f2 = top[t];		if (f1 != f2)		{			if (dep[f1] >= dep[f2])			{				Ans = max(Ans, getMax(1, 1, n, h[f1], h[s]));				s = f[f1];			}			else 			{				Ans = max(Ans, getMax(1, 1, n, h[f2], h[t]));				t = f[f2];			}		}		else		{			if (s == t) Ans = max(Ans, getMax(1, 1, n, h[s], h[s]));			else 			{				if (dep[s] >= dep[t]) Ans = max(Ans, getMax(1, 1, n, h[t], h[s]));				else Ans = max(Ans, getMax(1, 1, n, h[s], h[t]));			}		}	}}void querySum(int s, int t){	int f1, f2;	f1 = 0; f2 = 1;	while (f1 != f2)	{		f1 = top[s];		f2 = top[t];		if (f1 != f2)		{			if (dep[f1] >= dep[f2])			{				Ans += getSum(1, 1, n, h[f1], h[s]);				s = f[f1];			}			else 			{				Ans += getSum(1, 1, n, h[f2], h[t]);				t = f[f2];			}		}		else		{			if (s == t) Ans += getSum(1, 1, n, h[s], h[s]);			else 			{				if (dep[s] >= dep[t]) Ans += getSum(1, 1, n, h[t], h[s]);				else Ans += getSum(1, 1, n, h[s], h[t]);			}		}	}}int main(){//	freopen("1.in", "r", stdin);	scanf("%d", &n);	int a, b;	char flag[10];	for (int i = 1; i <= n - 1; i++)	{		scanf("%d%d", &a, &b);		addedge(a, b);		addedge(b, a);	}	for (int i = 1; i <= n; i++) scanf("%d", &W[i]);	DFS_1(1, 1, 0);	topH = 0; top[1] = 1; DFS_2(1);	buildTree(1, 1, n);	scanf("%d", &q);	for (int i = 1; i <= q; i++)	{		scanf("%s%d%d", flag, &a, &b);		if (!strcmp(flag, "QMAX"))		{			Ans = -999999999;			queryMax(a, b);			printf("%d\n", Ans);		}		else if (!strcmp(flag, "QSUM"))		{			Ans = 0;			querySum(a, b);			printf("%d\n", Ans);		}		else         //Change one node		{			change(1, 1, n, h[a], b);		}	}	return 0;}