[ABC362] F - Perfect Matching on a Tree

F - Perfect Matching on a Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 550 分

题面

给定 个顶点的树 。顶点编号为 到 ，第 条边 双向连接顶点 和 。

利用 ，定义一个具有 个顶点的完全图 如下：

• 中连接顶点 和 的边的权重 是 中顶点 和 之间的最短距离。

在 中找到一个最大权重最大匹配。即，找到一个由 对顶点组成的集合
，使得每个顶点 最多出现在 中一次，并且 被最大化。

限制条件

• 输入图是一棵树。
• 所有输入值均为整数。

---

输入

从标准输入中以以下格式给出输入：

输出

以以下格式打印解 。如果存在多个解，则任何一个都可接受。

---

输入样例 1

4
1 2
2 3
3 4

输出样例 1

2 4
1 3

在 中，顶点 和 之间的距离是 ，顶点 和 之间的距离是 ，因此匹配 的权重为 。不存在权重大于 的匹配，因此这是最大权重最大匹配。其他可接受的输出包括：

3 4
2 1

和

1 3
2 4

---

输入样例 2

3
1 2
2 3

输出样例 2

1 3

在 中，顶点 和 之间的距离是 ，因此匹配 的权重为 。不存在权重大于 的匹配，因此这是最大权重最大匹配。另一个可接受的输出为：

3 1