[HEOI2015]兔子与樱花

贪心

题面

一棵$n$个点带点权树上，所有点点权和儿子数之和不能超过$m$。每删去一结点，它的父亲将继承该结点的权值和所有儿子。问在满足要求的前提下能删多少个点。

• $n\leq2*10^6,m\leq10^5$

解析

删去一个结点，好处不用说，坏处是父亲可能不能被删了。但是，它父亲的父亲不会受到影响。所以删点顶多以一换一，稳赚不赔。
为了使删点数尽可能多，在每个结点下对儿子贡献排个序，从小取到大即可。

注意统计儿子贡献过程不能与向下递归步骤写在一起。这样下面的贡献会覆盖上面的。
如

il void dfs(re int u,re int fa)
{
  int sta[1000],top=0;c[u]+=k[u];
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u);
      sta[++top]=c[v]-1; 
    }
  sort(sta+1,sta+top+1);
  fp(i,1,top) if(c[u]+sta[i]<=m) c[u]+=sta[i],ans++;
  else break;
}

下面是对比，咕咕咕

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e6+100;
struct Edge{int to,nxt;}e[N<<1];
int n,m,c[N],k[N],h[N],cnt,sz[N],ans,sta[N];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
/*强调
il void dfs(re int u)
{
  int top=0;c[u]+=k[u];
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      dfs(v); 
    }
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      sta[++top]=c[v]-1;
    }
  sort(sta+1,sta+top+1);
  fp(i,1,top) if(c[u]+sta[i]<=m) c[u]+=sta[i],ans++;
  else break;
}
*/
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();m=gi();
  fp(i,1,n) c[i]=gi();
  fp(i,1,n)
    {
      k[i]=gi();
      fp(j,1,k[i])
    {
      re int v=gi()+1;
      add(i,v);
    }
    }
  dfs(1);
  printf("%d\n",ans);
  return 0;
}