一棵树上有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<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;#define lc o<<1#define rc o<<1|1#define m ((l+r)>>1)#define lson o<<1,l,m#define rson o<<1|1,m+1,rconst int N=3e4+5,INF=1e9;int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}    return x*f;}int n,a,b,w[N],q;char s[10];struct edge{    int v,ne;}e[N<<1];int h[N],cnt;inline void ins(int u,int v){    cnt++;    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;    cnt++;    e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;}int deep[N],size[N],fa[N],mx[N];void dfs1(int u){    size[u]=1;    for(int i=h[u];i;i=e[i].ne){        int v=e[i].v;        if(v==fa[u]) continue;        fa[v]=u;deep[v]=deep[u]+1;        dfs1(v);        size[u]+=size[v];        if(size[v]>size[mx[u]]) mx[u]=v;    }}int tid[N],top[N],tot;void dfs2(int u,int anc){    if(!u) return;    tid[u]=++tot;top[u]=anc;    dfs2(mx[u],anc);    for(int i=h[u];i;i=e[i].ne)        if(e[i].v!=mx[u]&&e[i].v!=fa[u]) dfs2(e[i].v,e[i].v);}struct node{    int sum,mx;}t[N<<2];void merge(int o){    t[o].sum=t[lc].sum+t[rc].sum;    t[o].mx=max(t[lc].mx,t[rc].mx);}void build(int o,int l,int r){    if(l==r) t[o].sum=t[o].mx=w[l];    else{        build(lson);        build(rson);        merge(o);    }}void change(int o,int l,int r,int p,int v){    if(l==r) t[o].sum=t[o].mx=v;    else{        if(p<=m) change(lson,p,v);        else change(rson,p,v);        merge(o);    }}int segsum(int o,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return t[o].sum;    else{        int ans=0;        if(ql<=m) ans+=segsum(lson,ql,qr);        if(m<qr) ans+=segsum(rson,ql,qr);        return ans;    }}int segmx(int o,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return t[o].mx;    else{        int mx=-INF;        if(ql<=m) mx=max(mx,segmx(lson,ql,qr));        if(m<qr) mx=max(mx,segmx(rson,ql,qr));        return mx;    }}int qmax(int x,int y){    int mx=-INF;    while(top[x]!=top[y]){        if(deep[top[x]]<deep[top[y]]) swap(x,y);        mx=max(mx,segmx(1,1,n,tid[top[x]],tid[x]));        x=fa[top[x]];    }    if(tid[x]>tid[y]) swap(x,y);    mx=max(mx,segmx(1,1,n,tid[x],tid[y]));    return mx;}int qsum(int x,int y){    int sum=0;    while(top[x]!=top[y]){        if(deep[top[x]]<deep[top[y]]) swap(x,y);        sum+=segsum(1,1,n,tid[top[x]],tid[x]);        x=fa[top[x]];    }    if(tid[x]>tid[y]) swap(x,y);    sum+=segsum(1,1,n,tid[x],tid[y]);    return sum;}int main(){    n=read();    for(int i=1;i<=n-1;i++) a=read(),b=read(),ins(a,b);    dfs1(1);dfs2(1,1);    for(int i=1;i<=n;i++) w[tid[i]]=read();        build(1,1,n);//tot==n    q=read();    while(q--){        scanf("%s",s);a=read();b=read();        if(s[1]==‘M‘) printf("%d\n",qmax(a,b));        else if(s[1]==‘S‘) printf("%d\n",qsum(a,b));        else w[a]=b,change(1,1,n,tid[a],b);    }}