不难发现此题是一道动态$dp$题
考虑此题没有修改怎么做，令$f[i]$表示让以$i$为根的子树被覆盖的最小花费，不难推出$f[i]=min(\sum_{j∈son[i]} f[j],val[i])$。
依然采用树链剖分+线段树维护每一条链。线段树上每个节点维护$val1$和$val2$两个值。
其中$val1$表示$\sum_{(fa[i]∈U)\&(i∉V)}f[i]$。U为该区间上点的点集，V为该区间所在链的点集。
$val2$表示以区间右端点为根的子树被覆盖的最小代价。
这东西随便维护一下就可以了（详见代码）
修改的话，我们先更新一下当前节点所在的链值，并将这个更新传递到上一条链去即可。
#include<bits/stdc++.h>
#define M 200005
#define mid ((a[x].l+a[x].r)>>1)
#define L long long
using namespace std; struct edge{int u,next;}e[M*]={}; int head[M]={},use=;
void add(int x,int y){use++;e[use].u=y;e[use].next=head[x];head[x]=use;} int dfn[M]={},rec[M]={},siz[M]={},fa[M]={},son[M]={},top[M]={},dn[M]={},t=;
void dfs(int x){
siz[x]=;
for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa[x]){
fa[e[i].u]=x; dfs(e[i].u);
siz[x]+=siz[e[i].u]; if(siz[son[x]]<siz[e[i].u]) son[x]=e[i].u;
}
}
void dfs(int x,int Top){
dfn[x]=++t; rec[t]=x; top[x]=Top;
if(son[x]) dfs(son[x],Top),dn[x]=dn[son[x]]; else dn[x]=x;
for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa[x]&&e[i].u!=son[x]) dfs(e[i].u,e[i].u);
}
L f[M]={},val[M]={};
void dp(int x){
if(dn[x]==x) f[x]=val[x];
for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa[x]) dp(e[i].u),f[x]+=f[e[i].u];
f[x]=min(f[x],val[x]);
} struct mat{
L f,g; mat(){f=g=;}
mat(L F,L G){f=F; g=G;}
friend mat operator +(mat a,mat b){
mat c;
c.f=min(a.f,a.g+b.f);
c.g=min(a.g+b.g,c.f);
return c;
}
}wei[M];
struct seg{int l,r; mat s;}a[M<<];
void pushup(int x){a[x].s=a[x<<].s+a[x<<|].s;} void build(int x,int l,int r){
a[x].l=l; a[x].r=r;
if(l==r){
L G=; int u=rec[l];
for(int i=head[u];i;i=e[i].next)
if(e[i].u!=fa[u]&&e[i].u!=son[u]){
G+=f[e[i].u];
}
a[x].s=wei[l]=mat(val[u],G);
return;
}
build(x<<,l,mid); build(x<<|,mid+,r);
pushup(x);
}
void updata(int x,int k){
if(a[x].l==a[x].r) return void(a[x].s=wei[k]);
if(k<=mid) updata(x<<,k); else updata(x<<|,k);
pushup(x);
}
mat query(int x,int l,int r){
if(l<=a[x].l&&a[x].r<=r) return a[x].s;
if(r<=mid) return query(x<<,l,r);
if(mid<l) return query(x<<|,l,r);
return query(x<<,l,r)+query(x<<|,l,r);
}
mat query(int x){return query(,dfn[top[x]],dfn[dn[x]]);} void Updata(int x,L Val){
wei[dfn[x]].f+=Val; val[x]+=Val;
while(x){
mat last=query(x);
updata(,dfn[x]);
mat now=query(x); x=fa[top[x]]; if(!x) return; wei[dfn[x]].g+=now.f-last.f;
}
} int n;
main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lld",val+i);
for(int i=,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs();
dfs(,);
dp();
build(,,n);
int m; scanf("%d",&m);
while(m--){
char op[]; L x,y;
scanf("%s%lld",op,&x);
if(op[]=='Q'){
mat res=query(,dfn[x],dfn[dn[x]]);
printf("%lld\n",res.f);
}else{
scanf("%lld",&y);
Updata(x,y);
}
}
}