首先是动态dp了嘛...
然后考虑怎么做：首先列出dp方程，大概长这样：
$f[i]=min(v[i],sum f[to])$
看着不太像动态dp呀...
考虑拿出重儿子的贡献，然后套模型，大概能构造出一个这样的东西：
设$g_{i}=sum f_{to}[to!=son]$
$egin{pmatrix} f_{i}\0 end{pmatrix}$ = $egin{pmatrix} g_{i}&v_{i}\ infty& 0 end{pmatrix}$ = $egin{pmatrix} f_{son}\0 end{pmatrix}$
然后套线段树维护矩阵即可
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #define rt1 (rt<<1) #define rt2 (rt<<1)|1 #define ll long long using namespace std; const ll inf=0x3f3f3f3fll; struct MAT { ll a[2][2]; friend MAT operator * (MAT x,MAT y) { MAT ret; ret.a[0][0]=min(x.a[0][0]+y.a[0][0],x.a[0][1]+y.a[1][0]); ret.a[0][1]=min(x.a[0][1]+y.a[1][1],x.a[0][0]+y.a[0][1]); ret.a[1][0]=min(x.a[1][1]+y.a[1][0],x.a[1][0]+y.a[0][0]); ret.a[1][1]=min(x.a[1][1]+y.a[1][1],x.a[1][0]+y.a[0][1]); return ret; } }ori[200005]; MAT tree[800005]; int ed[200005],dep[200005],nnum[200005],onum[200005],f[200005],ttop[200005],siz[200005],son[200005]; ll F[200005],G[200005],w[200005]; char s[2]; vector <int> v[200005]; int n,tot; void dfs(int x,int fx) { siz[x]=1,f[x]=fx,dep[x]=dep[fx]+1; for(int i=0;i<v[x].size();i++) { int to=v[x][i]; if(to==fx)continue; dfs(to,x); siz[x]+=siz[to],son[x]=(siz[to]>siz[son[x]])?to:son[x]; } } void redfs(int x,int fx,int topx) { ttop[x]=topx,nnum[x]=++tot,onum[tot]=x; if(son[x])redfs(son[x],x,topx),ed[x]=ed[son[x]]; else ed[x]=x,F[x]=G[x]=w[x]; F[x]=F[son[x]]; for(int i=0;i<v[x].size();i++) { int to=v[x][i]; if(to==fx||to==son[x])continue; redfs(to,x,to); G[x]+=F[to]; } F[x]=min(w[x],F[x]+G[x]); } void buildtree(int rt,int l,int r) { if(l==r) { int p=onum[l]; ori[p].a[0][0]=G[p],ori[p].a[1][0]=inf,ori[p].a[1][1]=0,ori[p].a[0][1]=w[p]; if(!son[p])ori[p].a[1][0]=0; tree[rt]=ori[p]; return; } int mid=(l+r)>>1; buildtree(rt1,l,mid),buildtree(rt2,mid+1,r); tree[rt]=tree[rt1]*tree[rt2]; } void update(int rt,int l,int r,int posi) { if(l==r){tree[rt]=ori[onum[posi]];return;} int mid=(l+r)>>1; if(posi<=mid)update(rt1,l,mid,posi); else update(rt2,mid+1,r,posi); tree[rt]=tree[rt1]*tree[rt2]; } MAT query(int rt,int l,int r,int lq,int rq) { if(l>=lq&&r<=rq)return tree[rt]; int mid=(l+r)>>1; if(rq<=mid)return query(rt1,l,mid,lq,rq); else if(lq>mid)return query(rt2,mid+1,r,lq,rq); else return query(rt1,l,mid,lq,rq)*query(rt2,mid+1,r,lq,rq); } void ins(int p,ll t) { ori[p].a[0][1]+=t-w[p]; if(!son[p])ori[p].a[0][0]+=t-w[p]; w[p]=t; while(p) { MAT m0=query(1,1,n,nnum[ttop[p]],nnum[ed[p]]); update(1,1,n,nnum[p]); MAT m1=query(1,1,n,nnum[ttop[p]],nnum[ed[p]]); p=f[ttop[p]]; if(!p)break; ori[p].a[0][0]+=m1.a[0][0]-m0.a[0][0]; } } inline int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(); for(int i=1;i<=n;i++)w[i]=read(); for(int i=1;i<n;i++) { int x=read(),y=read(); v[x].push_back(y),v[y].push_back(x); } dfs(1,0),redfs(1,0,1); buildtree(1,1,n); int m=read(); while(m--) { scanf("%s",s); if(s[0]=='Q') { int x=read(); MAT ret=query(1,1,n,nnum[x],nnum[ed[x]]); printf("%lld ",ret.a[0][0]); }else { int x=read(),y=read(); ins(x,w[x]+y); } } return 0; }