题目大意：一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。完成一些操作：

I. CHANGE u t : 把结点u的权值改为t

II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

注意：从点u到点v的路径上的节点包括u和v本身

树链剖分，维护点权

裸题但才开始一直WA，没看见还有负数。。。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=30005;
struct abcd  { int a,b,c; } v[N*2];
struct TREE  { int lc,rc,l,r,sum,max; } tree[N*4];
vector<int> to[N];
char s[7];
int n,totw,tot=1,t,x,y;
int vis[N],dep[N],fa[N],son[N],siz[N],top[N],w[N],val[N],c[N];
void DFS(int x)
{
	int t=0;
	vis[x]=1;dep[x]=dep[fa[x]]+1;
	for(int i=0;i<to[x].size();i++)
	{
		int y=to[x][i];
		if(!vis[y])
		{
			t=1;
			fa[y]=x;DFS(y);siz[x]+=siz[y];
			if(siz[y]>siz[son[x]]) son[x]=y;
		}
	}
}
void DFS2(int x)
{
	if(son[x])
	{
		top[son[x]]=top[x];
	    w[son[x]]=++totw;
	    DFS2(son[x]);
	}
	for(int i=0;i<to[x].size();i++)
	{
		int y=to[x][i];
		if(y!=fa[x]&&y!=son[x])
		{
			top[y]=y;
			w[y]=++totw;
			DFS2(y);
		}
	}
}
void build(int x,int l,int r)
{
	tree[x].l=l;tree[x].r=r;
	if(r==l)
	{
		tree[x].sum=val[l];
		tree[x].max=val[l];
		return;
	}
	int mid=(l+r)/2;
	tree[x].lc=++tot; build(tree[x].lc,l,mid);
	tree[x].rc=++tot; build(tree[x].rc,mid+1,r);
	tree[x].sum=tree[tree[x].lc].sum+tree[tree[x].rc].sum;
	tree[x].max=max(tree[tree[x].lc].max,tree[tree[x].rc].max);
}
void change(int x,int v,int d)
{
	if(tree[x].l==tree[x].r)
	{
		tree[x].sum=d;tree[x].max=d;return;
	}
	int mid=(tree[x].l+tree[x].r)/2;
	if(v<=mid) change(tree[x].lc,v,d);
	else change(tree[x].rc,v,d);
	tree[x].sum=tree[tree[x].lc].sum+tree[tree[x].rc].sum;
	tree[x].max=max(tree[tree[x].lc].max,tree[tree[x].rc].max);
}
int querysum(int x,int l,int r)
{
	if(l>r) swap(l,r);
	if(l<=tree[x].l&&tree[x].r<=r) return tree[x].sum;
	int mid=(tree[x].l+tree[x].r)/2;
	int ans=0;
	if(l<=mid) ans+=querysum(tree[x].lc,l,r);
	if(mid<r)  ans+=querysum(tree[x].rc,l,r);
	return ans;
}
int querymax(int x,int l,int r)
{
	if(l>r) swap(l,r);
	if(l<=tree[x].l&&tree[x].r<=r) return tree[x].max;
	int mid=(tree[x].l+tree[x].r)/2;
	int ans=-30000;
	if(l<=mid) ans=max(ans,querymax(tree[x].lc,l,r));
	if(mid<r)  ans=max(ans,querymax(tree[x].rc,l,r));
	return ans;
}
int Sum(int x,int y)
{
	int f1=top[x],f2=top[y];
	if(f1!=f2)
	{
		if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
		return querysum(1,w[f1],w[x])+Sum(fa[f1],y);
	}
	else return querysum(1,w[x],w[y]);
}
int Max(int x,int y)
{
	int f1=top[x],f2=top[y];
	if(f1!=f2)
	{
		if(dep[f1]<dep[f2]) {swap(x,y);swap(f1,f2);}
		return max(querymax(1,w[f1],w[x]),Max(fa[f1],y));
	}
	else return querymax(1,w[x],w[y]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&v[i].a,&v[i].b);
		to[v[i].a].push_back(v[i].b);
		to[v[i].b].push_back(v[i].a);
	}
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	for(int i=1;i<=n;i++) siz[i]=1;
	DFS(1);
	top[1]=1;w[1]=++totw;DFS2(1);
	for(int i=1;i<=n;i++) val[w[i]]=c[i];
	build(1,1,totw);
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		scanf("%s%d%d",&s,&x,&y);
		if(s[0]=='C') change(1,w[x],y);
		else if(s[1]=='M') printf("%d\n",Max(x,y));
		else printf("%d\n",Sum(x,y));
	}
}