每次dp很显然
要么所有儿子的，要么自己的
维护轻儿子的答案
注意先右儿子再左儿子
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define re register
#define pb push_back
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define poly vector<int>
#define bg begin
cs int mod=1e9+7,G=3;
cs ll inf=1e17;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline void Add(int &a,int b){(a+=b)>=mod?(a-=mod):0;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline void Dec(int &a,int b){(a-=b)<0?(a+=mod):0;}
inline int mul(int a,int b){return 1ll*a*b>=mod?1ll*a*b%mod:a*b;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline int ksm(int a,int b,int res=1){
for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));return res;
}
inline void chemx(ll &a,ll b){a<b?a=b:0;}
inline void chemn(ll &a,ll b){a>b?a=b:0;}
cs int N=200005;
vector<int> e[N];
int top[N],siz[N],son[N],ed[N],pos[N],idx[N],fa[N],dep[N],dfn;
int n,m;
void dfs1(int u){
siz[u]=1;
for(int &v:e[u]){
if(v==fa[u])continue;
fa[v]=u,dep[v]=dep[u]+1;
dfs1(v),siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
ll f[N],g[N],val[N];
void dfs2(int u,int tp){
pos[u]=++dfn,idx[dfn]=u,top[u]=tp,ed[u]=u,f[u]=val[u];
if(son[u]){
dfs2(son[u],tp);
ed[u]=ed[son[u]];
}
if(!son[u])g[u]=inf;
for(int &v:e[u]){
if(v==fa[u]||v==son[u])continue;
dfs2(v,v),g[u]+=f[v];
}
chemn(f[u],g[u]+f[son[u]]);
}
struct mat{
ll a[2][2];
mat(){a[0][0]=a[1][1]=a[1][0]=a[0][1]=inf;}
friend inline mat operator *(cs mat &a,cs mat &b){
mat c;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
if(a.a[i][j]!=inf)
for(int k=0;k<2;k++)
chemn(c.a[i][k],a.a[i][j]+b.a[j][k]);
return c;
}
}tr[N<<2],v[N];
namespace Seg{
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
inline void pushup(int u){
tr[u]=tr[rc]*tr[lc];
}
inline void build(int u,int l,int r){
if(l==r){tr[u]=v[idx[l]];return;}
build(lc,l,mid),build(rc,mid+1,r);
pushup(u);
}
inline void update(int u,int l,int r,int p){
if(l==r){tr[u]=v[idx[l]];return;}
if(p<=mid)update(lc,l,mid,p);
else update(rc,mid+1,r,p);
pushup(u);
}
inline mat query(int u,int l,int r,int st,int des){
if(st<=l&&r<=des)return tr[u];
if(des<=mid)return query(lc,l,mid,st,des);
if(mid<st)return query(rc,mid+1,r,st,des);
return query(rc,mid+1,r,st,des)*query(lc,l,mid,st,des);
}
#undef lc
#undef rc
#undef mid
}
using namespace Seg;
inline void pathupdate(int u){
while(u){
v[u].a[0][1]=val[u],v[u].a[1][1]=g[u];
update(1,1,n,pos[u]);
if(u==1)break;
g[fa[top[u]]]-=f[top[u]];
f[top[u]]=query(1,1,n,pos[top[u]],pos[ed[top[u]]]).a[0][1];
g[fa[top[u]]]+=f[top[u]],u=fa[top[u]];
}
}
char s[5];
int main(){
n=read();
for(int i=1;i<=n;i++)val[i]=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
e[u].pb(v),e[v].pb(u);
}
dfs1(1),dfs2(1,1);
for(int i=1;i<=n;i++)v[i].a[0][0]=0,v[i].a[1][1]=g[i],v[i].a[0][1]=val[i];
build(1,1,n);
m=read();
for(int i=1;i<=m;i++){
scanf("%s",s);
if(s[0]=='Q'){
int u=read();
cout<<query(1,1,n,pos[u],pos[ed[top[u]]]).a[0][1]<<'
';
}
else {
int u=read(),v=read();
val[u]+=v;pathupdate(u);
}
}
}