← 返回题目列表

AtCoder · arc183_d

D. 保持完美匹配

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

分数: 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