一棵树上有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”的操作，每行输出一个整数表示要求输出的结果。

#include<cstdio>#include<cstring>#include<iostream>#define lc k<<1#define rc k<<1|1#define IN inline#define R registerusing namespace std;const int N=3e5+10;IN int read(){    R int x=0;R bool f=1;    R char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=0;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}    return f?x:-x;}struct node{    int u,v,next;}e[N<<1];int n,m,T,tot,num,head[N],v[N],fa[N],top[N],pos[N],dep[N],siz[N],son[N];int mx[N<<2],sum[N<<2];void add(int x,int y){    e[++tot].u=x;    e[tot].v=y;    e[tot].next=head[x];    head[x]=tot;}void dfs(int u,int f,int de){    fa[u]=f;dep[u]=de;siz[u]=1;    for(int i=head[u],v;i;i=e[i].next){        v=e[i].v;        if(v!=f){            dfs(v,u,de+1);            siz[u]+=siz[v];            if(!son[u]||siz[son[u]]<siz[v]){                son[u]=v;            }        }    }}void getpos(int u,int tp){    top[u]=tp;    pos[u]=++num;    if(!son[u]) return ;    getpos(son[u],tp);    for(int i=head[u],v;i;i=e[i].next){        v=e[i].v;        if(v!=son[u]&&v!=fa[u]){            getpos(v,v);        }    }}void change(int k,int l,int r,int pos,int val){    if(l==r){        mx[k]=sum[k]=val;        return;    }    int mid=l+r>>1;    if(pos<=mid) change(lc,l,mid,pos,val);    else change(rc,mid+1,r,pos,val);    mx[k]=max(mx[lc],mx[rc]);    sum[k]=sum[lc]+sum[rc];}int qmax(int k,int l,int r,int x,int y){    if(l==x&&y==r) return mx[k];    int mid=l+r>>1;    if(y<=mid) return qmax(lc,l,mid,x,y);    else if(x>mid) return qmax(rc,mid+1,r,x,y);    else return max(qmax(lc,l,mid,x,mid),qmax(rc,mid+1,r,mid+1,y));}int findmax(int u,int v){    int tp1=top[u],tp2=top[v],ans=-0x3f3f3f3f;    while(tp1!=tp2){        if(dep[tp1]<dep[tp2]){            swap(tp1,tp2);            swap(u,v);        }        ans=max(ans,qmax(1,1,n,pos[tp1],pos[u]));        u=fa[tp1];tp1=top[u];    }    if(dep[u]>dep[v]) swap(u,v);    ans=max(ans,qmax(1,1,n,pos[u],pos[v]));    return ans;}int qsum(int k,int l,int r,int x,int y){    if(l==x&&y==r) return sum[k];    int mid=l+r>>1;    if(y<=mid) return qsum(lc,l,mid,x,y);    else if(x>mid) return qsum(rc,mid+1,r,x,y);    else return qsum(lc,l,mid,x,mid)+qsum(rc,mid+1,r,mid+1,y);}int findsum(int u,int v){    int tp1=top[u],tp2=top[v],ans=0;    while(tp1!=tp2){        if(dep[tp1]<dep[tp2]){            swap(tp1,tp2);            swap(u,v);        }        ans+=qsum(1,1,n,pos[tp1],pos[u]);        u=fa[tp1];tp1=top[u];    }    if(dep[u]>dep[v]) swap(u,v);    ans+=qsum(1,1,n,pos[u],pos[v]);    return ans;}int main(){    n=read();    for(int i=1,x,y,z;i<n;i++){        x=read();y=read();        add(x,y);add(y,x);    }    for(int i=1;i<=n;i++) v[i]=read();    dfs(1,0,1);    getpos(1,1);    for(int i=1;i<=n;i++) change(1,1,n,pos[i],v[i]);     char ch[20];    m=read();    for(int x,y;m--;){        scanf("%s",ch);x=read();y=read();        if(ch[0]==‘C‘){            change(1,1,num,pos[x],v[x]=y);        }        else{            if(ch[1]==‘M‘) printf("%d\n",findmax(x,y));            else printf("%d\n",findsum(x,y));        }    }    return 0;}