BZOJ 4712 洪水

本文主要是介绍BZOJ 4712 洪水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

小A走到一个山脚下，准备给自己造一个小屋。这时候，小A的朋友（op，又叫管理员）打开了创造模式，然后飞到山顶放了格水。于是小A面前出现了一个瀑布。作为平民的小A只好老实巴交地爬山堵水。那么问题来了：我们把这个瀑布看成是一个n个节点的树，每个节点有权值（爬上去的代价）。小A要选择一些节点，以其权值和作为代价将这些点删除（堵上），使得根节点与所有叶子结点不连通。问最小代价。不过到这还没结束。小A的朋友觉得这样子太便宜小A了，于是他还会不断地修改地形，使得某个节点的权值发生变化。不过到这还没结束。小A觉得朋友做得太绝了，于是放弃了分离所有叶子节点的方案。取而代之的是，每次他只要在某个子树中（和子树之外的点完全无关）。于是他找到你。

---

Input

输入文件第一行包含一个数n，表示树的大小。

接下来一行包含n个数，表示第i个点的权值。
接下来n-1行每行包含两个数fr，to。表示书中有一条边（fr，to）。
接下来一行一个整数，表示操作的个数。
接下来m行每行表示一个操作，若该行第一个数为Q，则表示询问操作，后面跟一个参数x，表示对应子树的根；若为C，则表示修改操作，后面接两个参数x，to，表示将点x的权值加上to。
n,m<=200000，保证任意to都为非负数

---

Output

对于每次询问操作，输出对应的答案，答案之间用换行隔开。

---

Solution

树剖优化dp。
点i的答案设为dp[i],权值设为a[i]
$dp[i]=min(a[i]，\sum dp[son])$
C操作只会增加x到根的儿子答案和，且有递增性。
那么维护每个点的$t[i]=a[i]-\sum dp[son]$，若t[i]<0则取a[i]，否则取$\sum dp[son]$
然后就随便维护了(

注意在一个点的dp从$\sum dp[son]$变成$a[i]$时向上的修改变为$to+a[i]-\sum dp[son]$，因为在dp过程中要突破a[i]需要耗费一定的修改量。(可以手摸看看)
所以要分段进行操作，但因为每个点只会改变一次取值，所以时间复杂度为$O(nlo{g}^{2}n)$

---

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{int y,nxt;
}e[400010];
int head[200010],cnt;
ll tree[4000010];
ll laz[4000010];
int dep[200010];
int son[200010];
int siz[200010]; 
int top[200010];
ll dis[200010];
ll dp[200010];
int id[200010];
int fa[200010];
int p[200010];
ll a[200010];
int n,m,rp,tot,ans;
bool flag;
void adde(int x,int y){cnt++;e[cnt].y=y;e[cnt].nxt=head[x];head[x]=cnt;
}
void build(int id,int l,int r){  if(l==r){  int x=p[l];laz[id]=dp[x];tree[id]=a[x]-dp[x];//cout<<l<<" "<<x<<" "<<tree[id]<<" "<<a[x]<<" "<<dp[x]<<endl;return;  }  int mid=(l+r)/2;  build(id*2,l,mid);  build(id*2+1,mid+1,r);  tree[id]=min(tree[id<<1],tree[id<<1|1]);
} 
void pushdown(int id,int l,int r){if(laz[id]){  tree[id<<1]-=laz[id];tree[id<<1|1]-=laz[id];laz[id<<1]+=laz[id];laz[id<<1|1]+=laz[id];laz[id]=0;}  
}  
int change(int id,int l,int r,int x,int y,int z){  int ans=0;int mid=(l+r)>>1;if(l<r) pushdown(id,l,r);if(x<=l&&r<=y){if(tree[id]>=z){tree[id]-=z;laz[id]+=z;return 0;}if(l==r){tree[id]-=z;laz[id]+=z;return p[l];}ans=change(id<<1|1,mid+1,r,x,y,z);if(ans){tree[id]=min(tree[id<<1],tree[id<<1|1]);return ans;}ans=change(id<<1,l,mid,x,y,z);tree[id]=min(tree[id<<1],tree[id<<1|1]);return ans;}if(y<=mid) ans=change(id<<1,l,mid,x,y,z); else if(x>mid) ans=change(id<<1|1,mid+1,r,x,y,z);  else{ans=change(id<<1|1,mid+1,r,x,y,z);if(ans==0) ans=change(id<<1,l,mid,x,y,z);}tree[id]=min(tree[id<<1],tree[id<<1|1]);return ans;
}  
ll question(int id,int l,int r,int x){  if(l<r) pushdown(id,l,r);  if(l==r){tree[id]=a[p[l]]-laz[id];return laz[id];}ll ans=0;int mid=(l+r)/2;  if(x<=mid) ans=question(id<<1,l,mid,x);  else ans=question(id<<1|1,mid+1,r,x);tree[id]=min(tree[id<<1],tree[id<<1|1]);  return ans;
} 
void dfs1(int x,int father,int depth){//cout<<x<<endl;siz[x]=1;fa[x]=father;dep[x]=depth;int maxn=-1;for(int i=head[x];i;i=e[i].nxt){int y=e[i].y;if(y==father) continue;dfs1(y,x,depth+1);dp[x]+=min(dp[y],a[y]);siz[x]+=siz[y];if(siz[y]>maxn){maxn=siz[y];son[x]=y;}}if(siz[x]==1) dp[x]=1e16;
}
void dfs2(int x,int ltop){id[x]=++tot; p[tot]=x;top[x]=ltop;if(!son[x]) return;dfs2(son[x],ltop);for(int i=head[x];i;i=e[i].nxt){int y=e[i].y;if(y==fa[x]||y==son[x])continue;dfs2(y,y);}
}
void update(int x,int z){int y=0;if(z<=0) return;while(x){y=change(1,1,n,id[top[x]],id[x],z);if(y) break;x=fa[top[x]];}if(y) update(fa[y],a[y]-question(1,1,n,id[y])+z);
}
int main(){ll z;int x,y;char op[2];scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);adde(x,y),adde(y,x);}dfs1(1,0,0),dfs2(1,1);//for(int i=1;i<=n;i++)//cout<<i<<" "<<a[i]<<" "<<dp[i]<<" "<<id[i]<<endl;//cout<<endl;build(1,1,n);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%s%d",op,&x);if(op[0]=='C'){scanf("%d",&y);a[x]+=y;z=question(1,1,n,id[x]);if(a[x]-y<z) update(fa[x],min(a[x],z)-min(a[x]-y,z));}else printf("%lld\n",min(question(1,1,n,id[x]),a[x]));}
}

这篇关于BZOJ 4712 洪水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---