CF2183D2 Tree Coloring (Hard Version)

这是该问题的 Hard 版本。不同之处在于，本题中你不仅需要求出最少操作次数，还需要输出一种达到该次数的染色方案。只有在你完成了所有版本的题目的情况下，才可以进行 Hack。 给定一棵 $n$ 个顶点的有根树 $^{\text{∗}}$，顶点编号为 $1$ 到 $n$，根节点编号为 $1$，所有顶点初始时均为白色。定义 $d_i$ 为根到第 $i$ 个顶点的距离。你可以进行如下操作任意多次： 1. 选择一组白色顶点组成的集合 $S$，要求集合内任意两个节点都不通过边相连，且到根节点的距离均不相同。即对任意 $x, y \in S$ 且 $x \neq y$，有 $d_x \neq d_y$ 且 $x$ 和 $y$ 间没有直接的边相连。 2. 将集合 $S$ 中的所有顶点染成黑色。 你的任务是求出将整棵树染黑所需的最小操作次数，并输出一种达到该次数的具体操作方案。 $^{\text{∗}}$ 一棵树是一种无环连通图。有根树是指定定了一个特殊节点作为根的树。

每个测试点包含多组测试用例。第一行一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数。 每个测试用例的第一行输入一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示树的节点数。 接下来 $n-1$ 行，每行两个整数 $u_i$ 和 $v_i$（$1 \leq u_i,v_i \leq n$，$u_i \neq v_i$），表示第 $i$ 条边连接的两个端点。 保证给定的边集组成一棵树。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，请输出以下内容： - 第一行输出一个整数 $k$，表示你的操作次数（$1 \leq k \leq n$）。 - 接下来 $k$ 行，每行以一个整数 $m$ 开头，表示本次操作的集合大小（$0 \leq m \leq n$）。随后 $m$ 个数，表示本次操作要染成黑色的节点 $u_1,u_2,\ldots,u_m$（$1 \leq u_i \leq n$）。 你需要保证： - 每次操作都是合法的。 - 每个节点只能被染黑一次（同一个操作或不同操作都不能重复染同一个节点）。 - 所有操作结束后，所有节点都被染成黑色。 - 你输出的操作次数 $x$，是所有可行解中最小的。 如果存在多组方案，输出任意一种均可。

在第一个测试用例中，$d_1=1$，$d_2=d_3=d_4=d_5=2$。可以证明至少需要 $5$ 次操作，因为任意两个节点都不能同时操作。 在第二个测试用例中，可以证明最少需要 $4$ 次操作染黑整棵树。示例输出展示了一种用 $4$ 步完成染色的方法。 由 ChatGPT 5 翻译