[洛谷 4107][HEOI2015]兔子与樱花

题目链接

https://www.luogu.com.cn/problem/P4107

题解

定义删除一个点 \(u\) 的代价为：\(son(u)+a_u-1\)。

一种比较显然的做法是：对于每个点 \(u\)，贪心地先删代价较小的儿子。

但有个问题：会不会出现删除 \(u\) 本身比删除 \(u\) 的儿子节点更优的情况呢？

其实不会。表面上看我们因为删除了 \(u\) 的儿子节点，导致可能不能再删除 \(u\)，但是这一操作只让我们少删了最多一个点。而如果能删除子节点的话，至少可以删掉一个子节点。可见我们的贪心策略不会导致最优解的丢失。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> e[2000005];
int son[2000005],a[2000005],l[2000005],r[2000005],id[2000005];
int ans,n,m,cnt;
bool cmp(int x,int y)
{
 return son[x]+a[x]<son[y]+a[y];
}
void dfs(int u)
{
 if(!son[u])return;
 for(auto v:e[u])
  dfs(v);
 sort(id+l[u],id+r[u]+1,cmp);
 for(int i=l[u];i<=r[u];i++)
 {
  int v=id[i];
  if(son[u]+a[u]+son[v]+a[v]-1<=m)
  {
   son[u]+=son[v]-1;
   a[u]+=a[v];
   ans++;
  }
 }
 return;
}
int main()
{
 ios::sync_with_stdio(false);
 cin>>n>>m;
 for(int i=0;i<n;i++)
  cin>>a[i];
 for(int i=0;i<n;i++)
 {
  cin>>son[i];
  l[i]=cnt+1,r[i]=cnt+son[i];
  for(int j=1;j<=son[i];j++)
  {
   int x;
   cin>>x;
   id[++cnt]=x;
   e[i].push_back(x);
  }
 }
 dfs(0);
 cout<<ans<<endl;
 return 0;
}