#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<iomanip> #include<algorithm> #include<ctime> #include<queue> #define rg register #define lst long long #define N 30050 #define ls (now<<1) #define rs (now<<1|1) using namespace std; int n,Q,cnt,ss,root,ans; struct EDGE{ int to,nxt; }edge[N<<1]; struct TREE{ int l,r,Max,sum; }ljl[N<<2]; int v[N],head[N]; int fa[N],deep[N],size[N],num[N]; int vv[N],top[N],son[N]; inline void add(rg int p,rg int q){edge[++cnt]=(EDGE){q,head[p]};head[p]=cnt;} inline int read() { rg int s=0,m=1;rg char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')m=-1,ch=getchar(); while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar(); return s*m; } inline void init() { n=read();root=1; for(rg int i=1;i<n;++i) { rg int p=read(),q=read(); add(p,q),add(q,p); } for(rg int i=1;i<=n;++i)v[i]=read(); } void dfs_1(rg int now,rg int fm,rg int dep) { rg int kk=0; fa[now]=fm,deep[now]=dep,size[now]=1; for(rg int i=head[now];i;i=edge[i].nxt) { rg int qw=edge[i].to; if(qw!=fm) { dfs_1(qw,now,dep+1); size[now]+=size[qw]; if(size[qw]>kk)kk=size[qw],son[now]=qw; } } } void dfs_2(rg int now,rg int up) { num[now]=++ss,vv[ss]=v[now],top[now]=up; if(son[now])dfs_2(son[now],top[now]); for(rg int i=head[now];i;i=edge[i].nxt) { rg int qw=edge[i].to; if(qw!=fa[now]&&qw!=son[now]) dfs_2(qw,qw); } } inline void Pushup(rg int now) { ljl[now].Max=max(ljl[ls].Max,ljl[rs].Max); ljl[now].sum=ljl[ls].sum+ljl[rs].sum; } void build(rg int now,rg int ll,rg int rr) { ljl[now]=(TREE){ll,rr}; if(ll==rr) { ljl[now].Max=ljl[now].sum=vv[ll]; return; } rg int mid=(ll+rr)>>1; build(ls,ll,mid),build(rs,mid+1,rr); Pushup(now); } void change(rg int now,rg int kk,rg int x) { if(ljl[now].l==kk&&ljl[now].r==kk) { ljl[now].Max=ljl[now].sum=x; return; } rg int mid=(ljl[now].l+ljl[now].r)>>1; if(kk<=mid)change(ls,kk,x); else change(rs,kk,x); Pushup(now); } int get_max(rg int now,rg int ll,rg int rr) { rg int ss=-1e9; if(ljl[now].l>=ll&&ljl[now].r<=rr)return ljl[now].Max; rg int mid=(ljl[now].l+ljl[now].r)>>1; if(rr<=mid)ss=max(ss,get_max(ls,ll,rr)); if(ll>mid) ss=max(ss,get_max(rs,ll,rr)); if(ll<=mid&&rr>mid)ss=max(ss,max(get_max(ls,ll,mid),get_max(rs,mid+1,rr))); return ss; } int get_sum(rg int now,rg int ll,rg int rr) { rg int ss=0; if(ljl[now].l>=ll&&ljl[now].r<=rr)return ljl[now].sum; rg int mid=(ljl[now].l+ljl[now].r)>>1; if(rr<=mid)ss+=get_sum(ls,ll,rr); if(ll>mid) ss+=get_sum(rs,ll,rr); if(ll<=mid&&rr>mid)ss+=get_sum(ls,ll,mid)+get_sum(rs,mid+1,rr); return ss; } inline void work(rg int x,rg int y,rg int op) { if(num[x]>num[y])swap(x,y); if(!op)ans=max(ans,get_max(1,num[x],num[y])); if(op) ans+=get_sum(1,num[x],num[y]); } inline void Work(rg int x,rg int y,rg int op) { while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]])swap(x,y); work(top[x],x,op); x=fa[top[x]]; } work(x,y,op); } inline void Ans() { Q=read(); for(rg int i=1;i<=Q;++i) { char type[6];cin>>type; rg int x=read(),y=read(); if(type[3]=='N'){ change(1,num[x],y);}//change if(type[3]=='X'){ans=-1e9;Work(x,y,0);printf("%d ",ans);}//qmax if(type[3]=='M'){ans=0; Work(x,y,1);printf("%d ",ans);}//qsum } } int main() { init(); dfs_1(root,0,0); dfs_2(root,root); build(1,1,n); Ans(); return 0; }