有一棵 $n$ 个节点的有根树，$1$ 号点为根节点。$i$ 的父节点为 $f_i$ ($1 \leq f_i < i \leq n$)。
你每星期可以选择不超过 $m$ 个节点删掉，需要保证被删掉的节点是没有父节点的。删完后，会剩下一个森林 (若干棵树)。
求最少多少星期才能删完所有的节点。
第一行包含两个正整数 $n, m$ ($1 \leq m \leq n$)。
第二行包含 $n - 1$ 个正整数 $f_2, f_3, \cdots, f_n$ ($1 \leq f_i < i$)。
第一行输出一个整数 $t$，表示最少需要的时间。
接下来 $t$ 行，第 $i$ 行表示第 $i$ 星期删的点，其中第一个整数 $s_i$ 表示这周删的点的个数，接下来 $s_i$ 个整数分别是这周肝的点的标号。
花式贪心水题...
这题有各种各样的贪心都能过，下面仅举一例：
用 $size_x$ 表示以 $x$ 为根的子树大小。每次选所有能选的点 (即没有父节点的点) 中 $size$ 最大的 $m$ 个 (若不足 $m$ 个则全选)，即为最优解。
下面我们分几步来证明这个结论 (ps: 证明的时候不需要用到这么强的条件，因而也可以说明有很多贪心算法都是对的)。
我们用 $S_i$ 表示操作序列 $S$ 中第 $i$ 步 (星期) 删掉的点的集合。
先证明两个引理：
(中间值引理) 对于一个 $K$ 步的操作序列，设 $\left| S_i \right| = a, \left| S_{i+1} \right| = b$ ($a \geq b$)。则对于 $\forall u, v$，只要 $u + v = a + b \wedge u, v \in \left[ a, b \right]$，存在另一个 $K$ 步的操作序列，使得 $S$ 与 $S'$ 仅有第 $i$ 步和第 $i + 1$ 步不同且 $\left| S'_i \right| = u, \left| S'_{i+1} \right| = v$。
(听说这需要证明？)
容易发现，第 $i$ 步操作的 $a$ 个点至少有 $a - b$ 个不支配第 $i + 1$ 步操作的第 $b$ 个点。于是这 $b$ 个点可以 "咕" 到第 $i + 1$ 步去操作。
(平移引理) 对于一个 $K$ 步的操作序列，$\forall i, \left| S_i \right| \neq \varnothing$。则存在另一个与之等效的 $K$ 步操作序列，满足对 $1 \leq i < K$，$\left| S'_i \right| \leq \left| S_{i+1} \right|$。
若 $\left| S'_i \right| > \left| S_{i+1} \right|$，则容易验证 $\left| S'_i \right|$ 和 $\left| S'_{i+1} \right|$ 之间满足 "中间值引理" 的条件，不断使用中间值原理即可。
现在假设存在一个序列 $B$，可以在 $K$ 步之内消完所有的点。我们证明，采用最开始的策略 $S$ (选 $size$ 最大的 $m$ 个)，也一定能在 $K$ 步之内消完。
不妨设原树是棵森林，则 $S_1, B_1$ 一定是森林中若干个树根的集合。现在假设 $S_1 \neq B_1$。
如果 $\left| B_1 \right| < m$，且 $\left| B_1 \right|$ 不等于森林中树的个数，则这个策略显然是不优的。
因此，要么 $\left| B_1 \right|$ 等于森林中树的个数，要么 $\left| B_1 \right| = m$。
而前者必有 $S_1 = B_1$。因此只需考虑后者。
我们设 $B_1$ 中 $size$ 最小者为 $X$，我们考虑消完 $X$ 需要几步。
如果消完 $X$ 需要恰好 $K$ 步，说明 $X$ 所在的树 $tree_X$ 的大小 $size_X$ 至少为 $K$。考虑其余 $m - 1$ 个子树，由于 $size_X$ 为其中最小者，因此剩下 $m - 1$ 棵子树的大小均不小于 $K$。
而在 $m \cdot K$ 步可以消完所有的节点，因此每个子树的大小恰好为 $K$。
而在这个时候，结论是平凡的，容易证明最优解一定是 $K$ 步。
因此，下面只需讨论消完 $X$ 不足 $K$ 步的情形。
设 $p$ 满足 $B_p$ 中没有 $tree_X$ 中的点的最小者。
考虑整个操作序列 $B$ 中，将所有 $tree_X$ 中的点提取出来，得到 $tree_X$ 的一个操作序列，下记为 $B_X$。
则 $\left( B_X \right)_p = \varnothing$。
对子序列 $B_X \left[ 1 .. p - 1 \right]$ 使用平移引理，将其平移到 $B'_X \left[ 2 .. p \right]$，则 $\left| \left( B'_X \right)_i \right| \leq \left| \left( B_X \right)_i \right|$ ($1 \leq i < p$)，特别地，$\left( B'_X \right)_1 = \varnothing$。
将新序列 $B'_X$ 与原序列 $B \setminus B_X$ "拼接"，得到一个序列 $B'$ (可能不合法)，我们最后需要将其变为一个合法序列。
注意到我们只需要在前若干步补几个元素即可，而这些多出来的元素均在后面。
如果前面某一步不足 $m$ 个，则由于树的数量 $\geq m$，因此一定存在一个没有使用的节点，将其首次使用的位置提升到这里即可。
最后再对 $X$ 使用中间值原理，将整个序列补平衡就可以了。
不断操作，直到最后序列 $B$ 与 $S$ 完全相同。
综上所述，$S$ 也能在 $K$ 步内完成。因此，这种贪心确实是正确的。
#include <bits/stdc++.h>
typedef std::pair <int, int> pr;
typedef std::priority_queue <pr> prio_que;
const int N = 100054;
int n, K;
int p[N], fc[N], nc[N];
int size[N], buf[N], len[N];
prio_que pq;
inline void link(int x, int px) {nc[x] = fc[px], fc[px] = x;}
int main() {
int i, v, tot = 0, *f = buf;
scanf("%d%d", &n, &K);
for (i = 2; i <= n; ++i) scanf("%d", p + i), link(i, p[i]);
for (i = n; i; --i) size[p[i]] += ++size[i];
for (pq.emplace(size[1], 1); !pq.empty(); f += len[tot++]) {
int &cnt = len[tot];
for (i = K; !pq.empty() && i; --i) f[cnt++] = pq.top().second, pq.pop();
for (i = 0; i < cnt; ++i)
for (v = fc[f[i]]; v; v = nc[v]) pq.emplace(size[v], v);
}
printf("%d\n", tot);
for (f = buf, i = 0; i < tot; f += len[i++], putchar(10))
for (printf("%d", len[i]), v = 0; v < len[i]; ++v)
printf(" %d", f[v]);
return 0;
}
坑1：注意在优先队列操作的时候要先 pop 完再 push 子节点哦~