题解 P4107 【[HEOI2015]兔子与樱花】
YoungNeal
2018-05-24 19:21:18
题解在博客[食用](https://www.cnblogs.com/YoungNeal/p/9084704.html)效果更佳哦~
## Solution
做法:自底向上,贪心的优先删除每个点的儿子中代价最小的一个。
贪心:以 $sons[i]+c[i]$ 为 $i$ 点的代价,每个点我们选取代价最小的删除,结果一定不会变差。
> 证明:对于 $i$ 点和 $i$ 的两个儿子 $j,p$,假设 $c[j]+sons[j]<c[p]+sons[p]$,由决策包容性,选 $j$ 优先删除一定比选 $p$ 优先删除更优。
自底向上:从根节点 $dfs$ ,从叶子结点向上回溯。路上如果遇到能删除的点就删,不必考虑其祖先。
> 证明:设点 $i$ 的儿子是 $j$ ,$j$ 的兄弟是 $p$ ,$j$ 还有一个儿子是 $q$。
>
> $dfs$ 的过程中,如果在回溯到 $j$ 的时候发现可以删除 $q$,那么就删除 $q$,并更新 $j$ 本身的代价,这样可能会导致无法再回溯到 $i$ 点的时候删除 $p$。
>
> 粗略想一下这不是有后效性嘛,但是因为贪心删了儿子而导致这个点不能再删,那么我们只会损失一个点,就是该点,而删除儿子至少会删除一个,所以不会亏。。
>
> 综上,自底向上的删除无后效性,满足贪心性质。
## Code
```cpp
#include<map>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define N 2000005
int n,m;
int ans;
int c[N];
int sons[N],cnt;
int tot[N],l[N],r[N];
inline char nc(){
static const int BS=1<<22;
static unsigned char buf[BS],*st,*ed;
if(st==ed) ed=buf+fread(st=buf,1,BS,stdin);
return st==ed?EOF:*st++;
}
//#define nc getchar
inline int getint(){
char ch;
int res=0;
while(!isdigit(ch=nc()));
while(isdigit(ch)){
res=(res<<1)+(res<<3)+(ch^48);
ch=nc();
}
return res;
}
bool cmp(int a,int b){
return sons[a]+c[a]<sons[b]+c[b];
}
void dfs(int now){
if(!sons[now]) return;
for(int i=l[now];i<=r[now];i++)
dfs(tot[i]);
std::sort(tot+l[now],tot+r[now]+1,cmp);
for(int i=l[now];i<=r[now];i++){
if(c[tot[i]]+sons[tot[i]]+c[now]+sons[now]-1<=m){
ans++;
c[now]+=c[tot[i]];
sons[now]+=sons[tot[i]]-1;
}
else break;
}
}
signed main(){
n=getint(),m=getint();
for(int i=1;i<=n;i++)
c[i]=getint();
for(int i=1;i<=n;i++){
sons[i]=getint();
l[i]=cnt+1;
r[i]=cnt+sons[i];
for(int j=1;j<=sons[i];j++){
int a=getint()+1;
tot[++cnt]=a;
}
}
dfs(1);
printf("%d\n",ans);
return 0;
}
```