传送门
树链剖分好题。
考虑分开维护重儿子和轻儿子的信息。
令f[i]f[i]f[i]表示iii为根子树的最优值，h[i]h[i]h[i]表示iii重儿子的最优值，g[i]g[i]g[i]表示iii所有轻儿子的最优值之和。
那么显然有：f[i]=minf[i]=minf[i]=min{h[i]+g[i],val[i]h[i]+g[i],val[i]h[i]+g[i],val[i]}
然后发现这个可以用矩阵来表示。
然后直接用树链合并更新矩阵就行了。
代码：
#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
#define N 200005
#define ll long long
#define inf 2000000000000000000
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int cnt,tot,n,q,first[N],pred[N],num[N],fa[N],dep[N],top[N],siz[N],hson[N],bot[N];
struct edge{int v,next;}e[N<<1];
struct Node{
ll a[2][2];
Node(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=inf;}
inline Node operator*(const Node&t){
Node ret;
for(int i=0;i<2;++i)for(int j=0;j<2;++j)if(a[i][j]!=inf)for(int k=0;k<2;++k)ret.a[i][k]=min(ret.a[i][k],a[i][j]+t.a[j][k]);
return ret;
}
}a[N],T[N<<2];
ll val[N],g[N],f[N];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
void dfs1(int p){
siz[p]=1;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa[p])continue;
fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
if(siz[v]>siz[hson[p]])hson[p]=v;
}
}
void dfs2(int p,int tp){
top[p]=tp,pred[num[p]=++tot]=p,bot[tp]=p;
if(!hson[p]){f[p]=val[p],g[p]=inf;return;}
dfs2(hson[p],tp),f[p]=f[hson[p]],g[p]=0;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v!=fa[p]&&v!=hson[p])dfs2(v,v),g[p]+=f[v];
}
f[p]=min(f[p]+g[p],val[p]);
}
inline void build(int p,int l,int r){
if(l==r){T[p]=a[pred[l]];return;}
build(lc,l,mid),build(rc,mid+1,r),T[p]=T[rc]*T[lc];
}
inline void update(int p,int l,int r,int k){
if(l==r){T[p]=a[pred[l]];return;}
if(k<=mid)update(lc,l,mid,k);
else update(rc,mid+1,r,k);
T[p]=T[rc]*T[lc];
}
inline Node query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return T[p];
if(qr<=mid)return query(lc,l,mid,ql,qr);
if(ql>mid)return query(rc,mid+1,r,ql,qr);
return query(rc,mid+1,r,mid+1,qr)*query(lc,l,mid,ql,mid);
}
inline ll query(int p){return query(1,1,n,num[p],num[bot[top[p]]]).a[0][1];}
inline void change(int p){
while(p){
a[p].a[0][1]=val[p],a[p].a[1][1]=g[p],update(1,1,n,num[p]);
if(p==1)return;
g[fa[top[p]]]-=f[top[p]],f[top[p]]=query(top[p]);
g[fa[top[p]]]+=f[top[p]],p=fa[top[p]];
}
}
int main(){
n=read();
for(int i=1;i<=n;++i)val[i]=read();
for(int i=1,u,v;i<n;++i)u=read(),v=read(),add(u,v),add(v,u);
dfs1(1),dfs2(1,1);
for(int i=1;i<=n;++i)a[i].a[0][0]=0,a[i].a[0][1]=val[i],a[i].a[1][1]=g[i];
build(1,1,n),q=read();
while(q--){
int x,y;
char op[5];
scanf("%s",op);
if(op[0]=='Q')x=read(),printf("%d\n",query(x));
else x=read(),y=read(),val[x]+=y,change(x);
}
return 0;
}