A16501. 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{∗}}$ 一棵树是一种无环连通图。有根树是指定定了一个特殊节点作为根的树。
给定一棵 $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$。
每个测试用例的第一行输入一个整数 $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$，是所有可行解中最小的。
如果存在多组方案，输出任意一种均可。
- 第一行输出一个整数 $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$，是所有可行解中最小的。
如果存在多组方案，输出任意一种均可。
输入输出样例
输入 #1
10 5 3 1 1 2 5 1 4 1 5 3 2 2 4 2 5 1 2 5 3 4 4 1 5 1 1 2 5 2 5 3 1 2 1 3 4 5 1 3 1 5 4 3 2 4 13 2 1 3 2 4 2 5 4 6 3 7 1 8 5 9 6 10 4 11 7 12 8 13 10 10 5 7 8 1 1 10 2 8 8 4 9 4 6 1 5 3 7 8 10 7 6 3 7 6 9 7 1 9 8 5 1 3 10 9 2 1 4 10 10 6 2 8 4 10 7 5 1 2 7 10 10 9 9 1 7 3 10 6 8 9 7 4 10 5 9 4 2 3 8 6 5 1 5 1 10
输出 #1
5 1 3 1 2 1 5 1 4 1 1 4 2 3 1 1 4 1 5 1 2 4 1 4 2 5 3 1 2 1 1 3 2 4 2 2 5 3 1 1 3 2 3 2 2 5 4 1 1 3 5 9 12 10 11 2 4 8 6 4 1 4 13 5 3 7 4 4 2 9 3 10 3 4 5 6 2 7 1 1 8 4 2 7 9 3 5 3 2 4 4 6 10 8 1 1 4 4 6 3 8 9 3 4 5 1 1 7 2 10 2 3 4 7 3 4 5 3 8 9 10 3 2 6 1
说明/提示
在第一个测试用例中，$d_1=1$，$d_2=d_3=d_4=d_5=2$。可以证明至少需要 $5$ 次操作，因为任意两个节点都不能同时操作。
在第二个测试用例中，可以证明最少需要 $4$ 次操作染黑整棵树。示例输出展示了一种用 $4$ 步完成染色的方法。
在第二个测试用例中，可以证明最少需要 $4$ 次操作染黑整棵树。示例输出展示了一种用 $4$ 步完成染色的方法。