这个题看起来好神的感觉。实际上也好神。。。
我们可以考虑设 $f_u$ 表示以 $u$ 为根的子树中最多能删多少个点，
再设 $g_u$ 表示以 $u$ 为根的子树中删了 $f_u$ 个点之后，$u$ 的 $son(i) + c_i$ 的最小值。
然后就可以树形 Dp 啦。
转移的话，考虑 $u$ 的孙子及更后辈，有：
$$f_u += \sum_{v\in \{son_u\}}f_v$$
然后考虑可以 $u$ 的哪些儿子。
首先删掉一个点 $x$ 的话，会对 $fa_x$ 的载重产生 $g_x - 1$ 点个贡献，
所以我们就按照这个贡献来排序，然后贪心地从小到大来选择是否删掉这个点。
那么我们就能够对 $f_u$ 和 $g_u$ 进行转移了。
时间复杂度 $O(n\log n)$，应该是可以过的吧。。。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 2000000 + 5 int n, m, tot;
int C[N], Size[N], Head[N], F[N], G[N], q[N], T[N]; struct Edge
{
int next, node;
}h[N]; inline void addedge(int u, int v)
{
h[++ tot].next = Head[u];
Head[u] = tot;
h[tot].node = v;
} inline int getint()
{
char ch = '\n';
for (; ch > '' || ch < ''; ch = getchar()) ;
int res = ch - '';
for (ch = getchar(); ch >= '' && ch <= ''; ch = getchar())
res = (res << ) + (res << ) + ch - '';
return res;
} inline void Solve()
{
int l = , r = ;
q[] = ;
while (l <= r)
{
int z = q[l ++];
for (int i = Head[z]; i; i = h[i].next)
{
int d = h[i].node;
q[++ r] = d;
}
}
for (; r; r --)
{
int z = q[r];
F[z] = T[] = , G[z] = Size[z] + C[z];
for (int i = Head[z]; i; i = h[i].next)
{
int d = h[i].node;
F[z] += F[d];
T[++ T[]] = G[d] - ;
}
sort(T + , T + T[] + );
for (int i = ; i <= T[]; i ++)
{
if (G[z] + T[i] <= m)
G[z] += T[i], F[z] ++;
else break ;
}
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("4027.in", "r", stdin);
freopen("4027.out", "w", stdout);
#endif n = getint(), m = getint();
for (int i = ; i < n; i ++)
C[i] = getint();
for (int i = ; i < n; i ++)
{
Size[i] = getint();
for (int j = ; j <= Size[i]; j ++)
{
int d = getint();
addedge(i, d);
}
}
Solve();
printf("%d\n", F[]); #ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return ;
}
4027_Gromah