【HEOI2015】兔子与樱花（贪心）

首先想一下题目中的操作如何转化：

当一个节点被去掉之后，这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。

设当前节点为 \(u\)，\(u\) 的父节点为 \(fa\)，儿子个数为 \(son_u\)。那么当我们把节点 \(u\) 删去时，\(fa\) 的樱花数会加上 \(c_u\)，儿子个数会加上 \(son-1\)（减 \(1\) 是因为 \(u\) 本来是 \(fa\) 的儿子但被删去了）。

那么删去一个节点对其父亲的负载增加值就被我们算出来了，设为 \(val_i=c_u+son_u-1\)。

想了想 dp 做法没能想出来，于是想了一下贪心。

考虑从下往上贪心，设当前节点为 \(u\)，先递归处理删除 \(u\) 的子树内除了 \(u\) 和 \(u\) 的儿子的节点（不妨把这些节点称为孙子节点，尽管它们可能是 u 的孙子、曾孙子、曾曾孙子）的最大贡献，再考虑删除 \(u\) 的儿子的最大贡献，然后回溯。

如何处理删除 \(u\) 的儿子对 \(u\) 的贡献？我们可以把 \(u\) 的儿子按它们的负载（孙子节点被删完后的负载），然后从小往大地删除，直到不能删为止（\(u\) 的负载要大于 \(m\) 时）。这样就能保证在有限的负载增加值中删去最多的节点。

为什么从下往上贪心是对的？

我们先画个图：

结合上面这个图，认为贪心不正确的人就会说：有没有可能我在 \(u=2\) 的时候删去了 \(3\) 号节点，增加了 \(2\) 节点的负载。导致在 \(u=1\) 的时候 \(2\) 节点因为负载过大而不能被删去。想一想，发现要删除 \(2\) 节点可能要取消删除 \(2\) 子树内的很多个节点，才能删除 \(2\) 节点，这样会使删除的节点数减少或不变，所以不如直接从下往上贪心。

代码如下：

#include<bits/stdc++.h>

#define N 2000010

using namespace std;

int n,m,ans,val[N],a[N];
int cnt,head[N],nxt[N],to[N];

void adde(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

void dfs(int u)
{
	for(int i=head[u];i;i=nxt[i]) dfs(to[i]);//先递归
	int tot=0;
	for(int i=head[u];i;i=nxt[i]) a[++tot]=val[to[i]];//把每个子节点的负载值加入排序数组
	sort(a+1,a+tot+1);//排序
	for(int i=1;i<=tot;i++)
	{
		if(val[u]+a[i]-1<=m)//贪心取
		{
			val[u]+=a[i]-1;
			ans++;
		}
		else break;
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&val[i]);
	for(int i=1;i<=n;i++)
	{
		int k;
		scanf("%d",&k);
		val[i]=val[i]+k;//重新设置val
		for(int j=1;j<=k;j++)
		{
			int v;
			scanf("%d",&v);
			v++;//注意！
			adde(i,v);
		}
	}
	dfs(1);
	printf("%d\n",ans);
	return 0;
}