【bzoj4712】洪水动态dp

不难发现此题是一道动态$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$表示以区间右端点为根的子树被覆盖的最小代价。

这东西随便维护一下就可以了（详见代码）

修改的话，我们先更新一下当前节点所在的链值，并将这个更新传递到上一条链去即可。

  1 #include<bits/stdc++.h>
  2 #define M 200005
  3 #define mid ((a[x].l+a[x].r)>>1)
  4 #define L long long
  5 using namespace std;
  6 
  7 struct edge{int u,next;}e[M*2]={0}; int head[M]={0},use=0;
  8 void add(int x,int y){use++;e[use].u=y;e[use].next=head[x];head[x]=use;}
  9 
 10 int dfn[M]={0},rec[M]={0},siz[M]={0},fa[M]={0},son[M]={0},top[M]={0},dn[M]={0},t=0;
 11 void dfs(int x){
 12     siz[x]=1;
 13     for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa[x]){
 14         fa[e[i].u]=x; dfs(e[i].u);
 15         siz[x]+=siz[e[i].u]; if(siz[son[x]]<siz[e[i].u]) son[x]=e[i].u;
 16     }
 17 }
 18 void dfs(int x,int Top){
 19     dfn[x]=++t; rec[t]=x; top[x]=Top;
 20     if(son[x]) dfs(son[x],Top),dn[x]=dn[son[x]]; else dn[x]=x;
 21     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);
 22 }
 23 L f[M]={0},val[M]={0};
 24 void dp(int x){
 25     if(dn[x]==x) f[x]=val[x];
 26     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];
 27     f[x]=min(f[x],val[x]); 
 28 }
 29 
 30 struct mat{
 31     L f,g; mat(){f=g=0;}
 32     mat(L F,L G){f=F; g=G;}
 33     friend mat operator +(mat a,mat b){
 34         mat c;
 35         c.f=min(a.f,a.g+b.f);
 36         c.g=min(a.g+b.g,c.f);
 37         return c;
 38     }
 39 }wei[M];
 40 struct seg{int l,r; mat s;}a[M<<2];
 41 void pushup(int x){a[x].s=a[x<<1].s+a[x<<1|1].s;}
 42 
 43 void build(int x,int l,int r){
 44     a[x].l=l; a[x].r=r;
 45     if(l==r){
 46         L G=0; int u=rec[l];
 47         for(int i=head[u];i;i=e[i].next) 
 48         if(e[i].u!=fa[u]&&e[i].u!=son[u]){
 49             G+=f[e[i].u];
 50         }
 51         a[x].s=wei[l]=mat(val[u],G);
 52         return;
 53     }
 54     build(x<<1,l,mid); build(x<<1|1,mid+1,r);
 55     pushup(x);
 56 }
 57 void updata(int x,int k){
 58     if(a[x].l==a[x].r) return void(a[x].s=wei[k]);
 59     if(k<=mid) updata(x<<1,k); else updata(x<<1|1,k);
 60     pushup(x);
 61 }
 62 mat query(int x,int l,int r){
 63     if(l<=a[x].l&&a[x].r<=r) return a[x].s;
 64     if(r<=mid) return query(x<<1,l,r);
 65     if(mid<l) return query(x<<1|1,l,r);
 66     return query(x<<1,l,r)+query(x<<1|1,l,r);
 67 }
 68 mat query(int x){return query(1,dfn[top[x]],dfn[dn[x]]);}
 69 
 70 void Updata(int x,L Val){
 71     wei[dfn[x]].f+=Val; val[x]+=Val;
 72     while(x){
 73         mat last=query(x);
 74         updata(1,dfn[x]);
 75         mat now=query(x);
 76         
 77         x=fa[top[x]]; if(!x) return;
 78         
 79         wei[dfn[x]].g+=now.f-last.f;
 80     }
 81 }
 82 
 83 int n;
 84 main(){
 85     scanf("%d",&n);
 86     for(int i=1;i<=n;i++) scanf("%lld",val+i);
 87     for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
 88     dfs(1);
 89     dfs(1,1);
 90     dp(1);
 91     build(1,1,n);
 92     int m; scanf("%d",&m);
 93     while(m--){
 94         char op[10]; L x,y;
 95         scanf("%s%lld",op,&x);
 96         if(op[0]=='Q'){
 97             mat res=query(1,dfn[x],dfn[dn[x]]);
 98             printf("%lld
",res.f);
 99         }else{
100             scanf("%lld",&y);
101             Updata(x,y);
102         }
103     }
104 }

【bzoj4712】洪水 动态dp

【bzoj4712】洪水动态dp