分数: 800 点
问题陈述
有一棵树 N 顶点编号自 1 to N。 的 网格的 i第一条边连接顶点 A_i 和 B_i。 在这里, N 是偶数,而且这棵树具有完美匹配。 具体来说,对于每个 i (1 \leq i \leq N/2),保证 A_i=i \times 2-1 和 B_i=i \times 2.
您将执行以下操作 N/2 次:
- 选择两片叶子(度数完全一致的顶点 1)并将它们从树中删除。 这里,移除后的树必须仍然具有完美匹配。 在这个问题中,我们也将零顶点的图视为一棵树。
对于每个操作,其得分定义为两个选定顶点之间的距离(连接两个顶点的简单路径上的边数)。
显示使总分最大化的一个过程。 可以证明,总存在一个过程可以完成 N/2 运营受到这个问题的限制。
约束
- 2 \leq N \leq 250000
- N 是偶数。
- 1 \leq A_i < B_i \leq N (1 \leq i \leq N-1)
- A_i=i \times 2 -1, B_i=i \times 2 (1 \leq i \leq N/2)
- 给定的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
输出
按以下格式打印解决方案:
X_1 Y_1
X_2 Y_2
\vdots
X_{N/2} Y_{N/2}
在这里, X_i 和 Y_i 是在中选择的两个顶点 i-第次操作。 如果有多个解决方案,您可以打印其中任何一个。
示例输入 1
4 1 2 3 4 2 3
示例输出 1
4 1 2 3
示例输出中的过程如下:
- 第一个操作:删除顶点 4 和 1。剩下的树有顶点 2 和 3,完美搭配。本次操作的得分为 3.
- 第二个操作:删除顶点 2 和 3。剩下的树有零个顶点和完美匹配。本次操作的得分为 1.
- 总分是 3 + 1 = 4.
不可能使总分大于 4,因此此输出解决了此示例输入。
示例输入 2
8 1 2 3 4 5 6 7 8 2 3 1 5 1 7
示例输出 2
4 8 7 6 5 3 2 1
示例输入 3
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 8 4 11 5 12 7 13 11 14 9 13
示例输出 3
1 6 5 2 8 12 3 7 10 4 11 9 13 14
示例输入 4
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 8 10 16 18 16 19 5 9 10 17 2 13 7 14 3 7 3 12
示例输出 4
6 1 2 15 20 13 14 19 16 4 11 18 17 12 3 5 9 7 8 10