题目详情题解（0）讨论（0）提交记录（0）

CFCF2183D2.Tree Coloring (Hard Version)

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是该问题的 Hard 版本。不同之处在于，本题中你不仅需要求出最少操作次数，还需要输出一种达到该次数的染色方案。只有在你完成了所有版本的题目的情况下，才可以进行 Hack。

给定一棵 nn 个顶点的有根树 ∗^{\text{∗}}，顶点编号为 11 到 nn，根节点编号为 11，所有顶点初始时均为白色。定义 did_i 为根到第 ii 个顶点的距离。你可以进行如下操作任意多次：

  1. 选择一组白色顶点组成的集合 SS，要求集合内任意两个节点都不通过边相连，且到根节点的距离均不相同。即对任意 x,y∈Sx, y \in S 且 x≠yx \neq y，有 dx≠dyd_x \neq d_y 且 xx 和 yy 间没有直接的边相连。
  2. 将集合 SS 中的所有顶点染成黑色。

你的任务是求出将整棵树染黑所需的最小操作次数，并输出一种达到该次数的具体操作方案。

∗^{\text{∗}} 一棵树是一种无环连通图。有根树是指定定了一个特殊节点作为根的树。

输入格式

每个测试点包含多组测试用例。第一行一个整数 tt（1≤t≤1041 \leq t \leq 10^4），表示测试用例数。

每个测试用例的第一行输入一个整数 nn（2≤n≤2⋅1052 \leq n \leq 2 \cdot 10^5），表示树的节点数。

接下来 n−1n-1 行，每行两个整数 uiu_i 和 viv_i（1≤ui,vi≤n1 \leq u_i,v_i \leq n，ui≠viu_i \neq v_i），表示第 ii 条边连接的两个端点。

保证给定的边集组成一棵树。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每个测试用例，请输出以下内容：

  • 第一行输出一个整数 kk，表示你的操作次数（1≤k≤n1 \leq k \leq n）。
  • 接下来 kk 行，每行以一个整数 mm 开头，表示本次操作的集合大小（0≤m≤n0 \leq m \leq n）。随后 mm 个数，表示本次操作要染成黑色的节点 u1,u2,…,umu_1,u_2,\ldots,u_m（1≤ui≤n1 \leq u_i \leq n）。

你需要保证：

  • 每次操作都是合法的。
  • 每个节点只能被染黑一次（同一个操作或不同操作都不能重复染同一个节点）。
  • 所有操作结束后，所有节点都被染成黑色。
  • 你输出的操作次数 xx，是所有可行解中最小的。

如果存在多组方案，输出任意一种均可。

输入输出样例

  • 输入#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

说明/提示

在第一个测试用例中，d1=1d_1=1，d2=d3=d4=d5=2d_2=d_3=d_4=d_5=2。可以证明至少需要 55 次操作，因为任意两个节点都不能同时操作。

在第二个测试用例中，可以证明最少需要 44 次操作染黑整棵树。示例输出展示了一种用 44 步完成染色的方法。

首页