Description：

有一颗树，每个节点儿子节点的数量加这个点的权值不能超过给定的 $m$ ，如果删去这个点，那么这个点的儿子节点会挂在父亲节点上，这个点的权值也会加到父亲节点上，问整棵树最多能删几个点。

$1\le n \le 2000000$

Solution：

如果每个点代价不同，那么很可能是DP，如果每个点代价都为1，那么很可能是贪心。

如果知道是贪心的话那就不难想到把所有子节点按权值 $+$ 儿子节点个数排序选最小的删除，因为儿子节点的价值会全部转移到父节点上。

为什么是正确的呢？设 $f[i]$ 表示权值 $+$ 儿子节点个数，那么兄弟之间显然一定选 $f[i]$ 小的，关键问题是会不会因为这次选了 $i$ 而导致在父亲 $j$ 的父亲 $k$ 那里丢掉价值呢？并不会，因为设 $j$ 的兄弟为 $p$ ，若 $f[p]\le f[j]$ ，那么 $p$ 该选还会选，若 $f[p]>f[j]$ ，那么增加了 $j$ 的权值后最多只会挤掉一个，而之前已经选了一个 $i$ 所以不会更劣。

所以 $dfs$ 在回溯的时候把儿子节点排序贪心就行了。

Code：