这是问题的困难版本。版本之间的区别在于,在此版本中,您必须找到最少的操作数,并找到使用那么多操作为树着色的方法。只有解决了该问题的所有版本,您才能破解。
给你一个有根树$$$^{\text{*}}$$$,由$$$n$$$个顶点组成,编号从$$$1$$$到$$$n$$$,其中根的索引为$$$1$$$,每个顶点最初都是白色的。将 $$$d_i$$$ 定义为从根到第 $$$i$$$ 个顶点的距离。您可以多次执行以下操作:
- 选择白色顶点的子集 $$$S$$$,使得 $$$S$$$ 中没有两个节点通过边连接,或者到节点 $$$1$$$ 的距离相同。形式上,$$$S$$$ 应该满足所有 $$$x,y\in S$$$ 和 $$$x\neq y$$$、$$$d_x\neq d_y$$$,并且 $$$x$$$ 和 $$$y$$$ 之间没有边。
- 将顶点着色为 $$$S$$$ 黑色。
你的工作是找到将整棵树涂成黑色所需的最少操作数 并找到执行操作的方法.
$$$^{\text{*}}$$$树是没有环的连通图。 有根树是一棵树,其中一个顶点是特殊的,称为根。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) – 树中的顶点数。
$$$n-1$$$ 后面的第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$, $$$u_i\neq v_i$$$) — 第 $$$i$$$ 条边的末端。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^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$$$) 代表您在此操作中涂黑的 $$$m$$$ 节点。
您应该保证:
- 您所做的每项操作均有效。
- 您不能对同一顶点着色两次(在相同操作或不同操作中)。
- 在所有操作结束时,所有顶点都被涂成黑色。
- 您执行的操作数为 $$$x$$$,其中 $$$x$$$ 是所有可能解决方案的最小可能操作数。
如果有多个可能的解决方案,则输出任何一个。
示例
输入复制
1053 11 25 14 153 22 42 51 253 44 15 11 252 53 12 13 451 31 54 32 4132 13 24 25 46 37 18 59 610 411 712 813 10105 78 11 102 88 49 46 15 37 8107 63 76 97 19 85 13 109 21 41010 62 84 107 51 27 1010 99 17 3106 89 74 105 94 23 86 51 51 10
输出复制
51 31 21 51 41 142 3 11 41 51 241 42 5 31 21 132 4 22 5 31 132 3 22 5 41 135 9 12 10 11 24 8 6 4 14 13 5 3 744 2 9 3 103 4 5 62 7 11 842 7 93 5 3 24 4 6 10 81 144 6 3 8 93 4 5 11 72 10 234 7 3 4 53 8 9 103 2 6 1
注意
在第一个测试用例中,$$$d_1=1$$$ 和 $$$d_2=d_3=d_4=d_5=2$$$。我们可以证明,我们必须执行至少 $$$5$$$ 操作,因为没有两个节点可以同时操作。
在第二个测试用例中,我们可以证明为整个树着色所需的最少操作数为 $$$4$$$。示例输出显示了在 $$$4$$$ 操作中为其着色的一种方法。