一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身

　　输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

　　对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

4
1
2
2
10
6
5
6
5
16

题目分析:

树链剖分裸题 通过剖分把树的轻重链上号 扔进线段树里维护

deep[top[x]]>deep[top[y]]时，将x向上爬。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
struct your
{
	int x,y;
	int sum;
	int maxx;
}a[200000];
int net[61000],head[31000],to[61000];
int val[31000],top[31000],number[31000];
int fa[31000],size[31000],son[31000],deep[31000];
int tot,cnt;
char s[21];
void add(int x,int y)
{
	net[++tot]=head[x];
	to[tot]=y;
	head[x]=tot;
}
void dfs(int x,int temp)
{
	fa[x]=temp;
	deep[x]=deep[temp]+1;
	size[x]=1;
	for(int i=head[x];i;i=net[i])
	{
		if(to[i]==temp) continue;
		dfs(to[i],x);
		size[x]+=size[to[i]];
		if(size[son[x]]<size[to[i]]) son[x]=to[i];
	}
}
void dfs2(int x,int temp)
{
	number[x]=++cnt;
	top[x]=temp;
	if(son[x]) dfs2(son[x],temp);
	for(int i=head[x];i;i=net[i])
		if(to[i]!=son[x]&&to[i]!=fa[x])
			dfs2(to[i],to[i]);
}
void build(int dx,int dy,int num)
{
	a[num].x=dx,a[num].y=dy;
	if(dx==dy)
	{
		a[num].sum=val[dx];
		a[num].maxx=val[dx];
		return ;
	}
	int mid=(dx+dy)>>1;
	build(dx,mid,num<<1);
	build(mid+1,dy,num<<1|1);
	a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
	a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
}
void update(int dx,int c,int num)
{
	if(a[num].x==dx&&a[num].y==dx)
	{
		a[num].sum=c;
		a[num].maxx=c;
		return ;	
	}
	int mid=(a[num].x+a[num].y)>>1;
	if(dx<=mid) update(dx,c,num<<1);
	else update(dx,c,num<<1|1);
	a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
	a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
}
int askmax(int dx,int dy,int num)
{
	if(a[num].x==dx&&a[num].y==dy)
		return a[num].maxx;
	int mid=(a[num].x+a[num].y)>>1;
	if(dx>mid) return askmax(dx,dy,num<<1|1);
	if(dy<=mid) return askmax(dx,dy,num<<1);
	return max(askmax(dx,mid,num<<1),askmax(mid+1,dy,num<<1|1));
}
int asksum(int dx,int dy,int num)
{
	if(dx==a[num].x&&a[num].y==dy)
		return a[num].sum;
    int mid=(a[num].x+a[num].y)>>1;
    if(dy<=mid) return asksum(dx,dy,num<<1);
    if(dx>mid) return asksum(dx,dy,num<<1|1);
	return asksum(dx,mid,num<<1)+asksum(mid+1,dy,num<<1|1);
}
int findmax(int x,int y)
{
	int ans=0x3f3f3f3f;
	ans=-ans;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		ans=max(ans,askmax(number[top[x]],number[x],1));
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	ans=max(ans,askmax(number[x],number[y],1));
	return ans;
}
int findsum(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		ans+=asksum(number[top[x]],number[x],1);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	ans+=asksum(number[x],number[y],1);
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0);
	dfs2(1,1);
	for(int i=1;i<=n;i++) scanf("%d",&val[number[i]]);
	build(1,n,1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",&s[0]);
		int x,y,c;
		if(s[1]=='S')
		{
			scanf("%d%d",&x,&y);
			printf("%d\n",findsum(x,y));
		}
		else if(s[1]=='M')
		{
			scanf("%d%d",&x,&y);
			printf("%d\n",findmax(x,y));
		}
		else
		{
			scanf("%d%d",&x,&c);
			update(number[x],c,1);
		}
	}
    return 0;
}