看到数据范围就大概只能想到这一种做法了吧。

首先实际上是每个点的权值为v[i]=c[i]+son[i]，然后删除一个点就是v[fa[i]]+=v[i]-1。

从下往上贪心删，每次将节点的所有儿子按权值排序，从小到大能删就删，这样一定最优。

感性证明一下“若因为删了某个点而使祖先无法被删去，而删这个点及其子树的收益一定不小于1（因为这个点已经被删了），故一定不会更劣”

1 #include
     
       2 #include
      
        3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 #define For(i,x) for (int i=h[x]; i; i=nxt[i]) 5 using namespace std; 6  7 const int N=2000010; 8 int n,m,x,v,ans,cnt,c[N],a[N],to[N],nxt[N],h[N]; 9 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }10 11 void dfs(int x){12     int tot=0;13     For(i,x) dfs(to[i]);14     For(i,x) a[++tot]=c[to[i]];15     sort(a+1,a+tot+1);16     rep(i,1,tot) if (c[x]+a[i]-1<=m) c[x]+=a[i]-1,ans++; else break;17 }18 19 int main(){20     freopen("bzoj4027.in","r",stdin);21     freopen("bzoj4027.out","w",stdout);22     scanf("%d%d",&n,&m);23     rep(i,1,n) scanf("%d",&c[i]);24     rep(i,1,n){25         scanf("%d",&x); c[i]+=x;26         rep(j,1,x) scanf("%d",&v),v++,add(i,v);27     }28     dfs(1); printf("%d\n",ans);29     return 0;30 }