并不知道算不算动态DP.
对树进行树链剖分.
令 $\mathrm{f[x]}$ 表示 $\mathrm{x}$ 子树的答案.
令 $\mathrm{g[x]}$ 表示虚儿子答案之和.
然后有 $\mathrm{f[x]=min(v[x], g[x]+f[k])}$, 其中 $\mathrm{k}$ 为重儿子.
不难发现如果 $\mathrm{x}$ 选掉了,则 $\mathrm{x}$ 子树都不必选了.
那么对于一条重链链顶 $\mathrm{x}$ 的答案,一定是若干个 $\mathrm{g}$ 加上 $\mathrm{v}$.
这个就是最小前缀和的形式,可以用线段树来维护.
然后修改权值的时候暴力跳重链进行更新即可.
#include <cstdio> #include <cstring> #include <vector> #include <set> #include <map> #include <algorithm> #define N 200009 #define pb push_back #define ll long long #define ls now<<1 #define rs now<<1|1 #define setIO(s) freopen(s".in","r",stdin) using namespace std; const ll inf = 1ll << 40; vector<int>G[N]; int n , scc, bu[N], son[N], fa[N], top[N], st[N], ed[N], dep[N],size[N]; ll gx[N],fx[N],val[N]; struct data { ll g,mn; data() { g=0,mn=0; } data operator+(const data b) const { data c; c.mn=min(mn,g+b.mn); c.g=g+b.g; return c; } }s[N<<2]; void build(int l,int r,int now) { if(l==r) { s[now].mn=val[bu[l]]; s[now].g = gx[bu[l]]; return ; } int mid=(l+r)>>1; build(l,mid,ls); build(mid+1,r,rs); s[now]=s[ls]+s[rs]; } void update(int l,int r,int now,int p,ll v) { if(l == r) { s[now].mn = v; return ; } int mid=(l+r)>>1; if(p<=mid) { update(l,mid,ls,p,v); } else{ update(mid+1,r,rs,p,v); } s[now]=s[ls]+s[rs]; } void modify(int l,int r,int now,int p,ll v) { if(l == r) { s[now].g = v; return ; } int mid=(l+r)>>1; if(p<=mid) modify(l,mid,ls,p,v); else modify(mid+1,r,rs,p,v); s[now]=s[ls]+s[rs]; } data query(int l,int r,int now,int L,int R) { if(l>=L&&r<=R) { return s[now]; } int mid=(l+r)>>1; if(L<=mid&&R>mid) return query(l,mid,ls,L,R)+query(mid+1,r,rs,L,R); else if(L<=mid) return query(l,mid,ls,L,R); else return query(mid+1,r,rs,L,R); } void dfs1(int x, int ff) { size[x]=1; fa[x]=ff,dep[x]=dep[ff]+1; ll sum=0; for(int i=0;i<G[x].size();++i) { int v=G[x][i]; if(v==ff) continue; dfs1(v, x); sum+=fx[v]; size[x] += size[v]; if(size[v] > size[son[x]]) { son[x] = v; } } if(size[x]==1) { fx[x] = val[x]; } else { fx[x]=min((ll)val[x], sum); } } void dfs2(int x, int tp) { top[x]=tp; ed[x]=st[x]=++scc; bu[st[x]]=x; if(son[x]) { dfs2(son[x], tp); ed[x]=ed[son[x]]; } for(int i=0;i<G[x].size();++i) { int v=G[x][i]; if(v==son[x]||v==fa[x]) continue; gx[x]+=fx[v]; dfs2(v, v); } } int main() { // setIO("input"); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%lld",&val[i]); } for(int i=1;i<n;++i) { int x, y; scanf("%d%d",&x,&y); G[x].pb(y); G[y].pb(x); } dfs1(1, 0); dfs2(1, 1); build(1, n, 1); int m; scanf("%d",&m); for(int i=1;i<=m;++i) { char op[2]; int x,y,z; scanf("%s", op); if(op[0]=='Q') { scanf("%d",&x); printf("%lld\n",query(1, n, 1, st[x], ed[x]).mn); } else { scanf("%d%d",&x,&y); // val[x] -> y // val[x] -> y update(1, n, 1, st[x], val[x] += y); // 先修改了 x 的信息( val[x] ) // 先直接更新 x 处的东西. for(int i = top[x]; i ; i = top[fa[i]]) { ll tmp = query(1, n, 1, st[i], ed[i]).mn; if(fa[i]) { gx[fa[i]] = gx[fa[i]] - fx[i] + tmp; // 修改 fa[i] 的 g[i] modify(1,n,1,st[fa[i]],gx[fa[i]]); // 修改完父亲了. } fx[i] = tmp; } // 咱也不知道对不对啊...... } } return 0; }