← 返回题目列表

Codeforces · 2183/D2

D2. 树着色(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的区别在于,在此版本中,您必须找到最少的操作数,并找到使用那么多操作为树着色的方法。只有解决了该问题的所有版本,您才能破解。

给你一个有根树$$$^{\text{*}}$$$,由$$$n$$$个顶点组成,编号从$$$1$$$到$$$n$$$,其中根的索引为$$$1$$$,每个顶点最初都是白色的。将 $$$d_i$$$ 定义为从根到第 $$$i$$$ 个顶点的距离。您可以多次执行以下操作:

  1. 选择白色顶点的子集 $$$S$$$,使得 $$$S$$$ 中没有两个节点通过边连接,或者到节点 $$$1$$$ 的距离相同。形式上,$$$S$$$ 应该满足所有 $$$x,y\in S$$$ 和 $$$x\neq y$$$、$$$d_x\neq d_y$$$,并且 $$$x$$$ 和 $$$y$$$ 之间没有边。
  2. 将顶点着色为 $$$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$$$ 是所有可能解决方案的最小可能操作数。

如果有多个可能的解决方案,则输出任何一个。

示例

输入
复制

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

输出
复制

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$$$ 操作中为其着色的一种方法。