#include<iostream> #include<cstdio> using namespace std; const int N=500010; int n,head[N],tope=0,top[N],pos[N],fa[N],size[N],dep[N],son[N],a[N]; int tot=0,totw=1,ans=0; struct node{ int l,r,lc,rc,sum,ma; }t[N]; struct node2{ int to,next; }e[N]; inline int intt(int x,int y) { tope++; e[tope].next=head[x]; e[tope].to=y; head[x]=tope; } inline int dfs1(int x) { dep[x]=dep[fa[x]]+1; size[x]=1; for(int i=head[x];i;i=e[i].next) { int y=e[i].to; if(y!=fa[x]) { fa[y]=x; dfs1(y); size[x]+=size[y]; if(size[y]>size[son[x]]) son[x]=y; } } } inline int dfs2(int x,int f) { pos[x]=++tot; top[x]=f; if(son[x]) dfs2(son[x],f); for(int i=head[x];i;i=e[i].next) { int y=e[i].to; if(y!=fa[x]&&y!=son[x]) { dfs2(y,y); } } } inline void build(int x,int l,int r) { t[x].l=l;t[x].r=r; if(l==r) { t[x].sum=a[l]; t[x].ma=a[l]; return ; } int mid=(l+r)/2; t[x].lc=++totw; build(t[x].lc,l,mid); t[x].rc=++totw; build(t[x].rc,mid+1,r); t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum; t[x].ma=max(t[t[x].lc].ma,t[t[x].rc].ma); } inline void change(int x,int w,int d) { if(t[x].l==t[x].r) { t[x].sum=d; t[x].ma=d; return ; } int mid=(t[x].l+t[x].r)/2; if(w<=mid) change(t[x].lc,w,d); if(w>mid) change(t[x].rc,w,d); t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum; t[x].ma=max(t[t[x].lc].ma,t[t[x].rc].ma); } inline int maxx(int x,int l,int r) { if(l<=t[x].l&&t[x].r<=r) { return t[x].ma; } int mid=(t[x].l+t[x].r)/2,mm=-500000; if(l<=mid) mm=max(mm,maxx(t[x].lc,l,r)); if(r>mid) mm=max(mm,maxx(t[x].rc,l,r)); return mm; } inline int sum(int x,int l,int r) { if(l<=t[x].l&&t[x].r<=r) { return t[x].sum; } int mid=(t[x].l+t[x].r)/2,ss=0; if(l<=mid) ss+=sum(t[x].lc,l,r); if(r>mid) ss+=sum(t[x].rc,l,r); return ss; } int main() { scanf("%d",&n); for(int i=1;i<=n-1;++i) { int a,b; scanf("%d%d",&a,&b); intt(a,b); intt(b,a); } dfs1(1); dfs2(1,1); for(int i=1;i<=n;++i) { scanf("%d",&a[pos[i]]); } build(1,1,n); int m;char s[10]; scanf("%d",&m); int x,y,f1,f2; for(int i=1;i<=m;++i) { scanf("%s%d%d",s,&x,&y); if(s[0]=='C') change(1,pos[x],y); if(s[1]=='M') { ans=-500000; while(1) { f1=top[x];f2=top[y]; if(f1==f2) { if(pos[x]<pos[y]) ans=max(ans,maxx(1,pos[x],pos[y])); else ans=max(ans,maxx(1,pos[y],pos[x])); break; } else { if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2); ans=max(ans,maxx(1,pos[f1],pos[x])); x=fa[f1]; } } printf("%d\n",ans); } if(s[1]=='S') { ans=0; while(1) { f1=top[x];f2=top[y]; if(f1==f2) { if(pos[x]<pos[y])ans+=sum(1,pos[x],pos[y]); else ans+=sum(1,pos[y],pos[x]); break; } else { if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2); ans+=sum(1,pos[f1],pos[x]); x=fa[f1]; } } printf("%d\n",ans); } } return 0; }
|