首先想一下题目中的操作如何转化:
当一个节点被去掉之后,这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。
设当前节点为 \(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;
}
原文地址:http://www.cnblogs.com/ez-lcw/p/16837423.html