树上的最大权完美匹配

题目描述

给定一棵具有 $N$ 个顶点的树 $T$。顶点编号为 $1$ 到 $N$,第 $i$ 条边 $(1 \le i \le N-1)$ 双向连接顶点 $u_i$ 和 $v_i$。

利用 $T$ 定义如下具有 $N$ 个顶点的完全图 $G$:

$G$ 中顶点 $x$ 与顶点 $y$ 之间边的权值 $w(x, y)$ 等于顶点 $x$ 与 $y$ 在 $T$ 中的最短距离。

求 $G$ 中一个最大权最大匹配。也就是说,求一个由 $\lfloor N/2 \rfloor$ 对顶点组成的集合 $M = \{(x_1, y_1), (x_2, y_2), \dots, (x_{\lfloor N/2 \rfloor}, y_{\lfloor N/2 \rfloor})\}$,使得每个顶点 $1, 2, \dots, N$ 在 $M$ 中至多出现一次,并且 $\displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i, y_i)$ 最大。

输入格式

输入按以下格式从标准输入给出:

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

输出格式

按以下格式输出一个解 $\{(x_1, y_1), (x_2, y_2), \dots, (x_{\lfloor N/2 \rfloor}, y_{\lfloor N/2 \rfloor})\}$。若存在多个解,输出其中任意一个均可。

$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_{\lfloor N/2 \rfloor}$ $y_{\lfloor N/2 \rfloor}$

样例

4
1 2
2 3
3 4

2 4
1 3

在 $T$ 中,顶点 $2$ 与 $4$ 的距离为 $2$,顶点 $1$ 与 $3$ 的距离为 $2$,因此匹配 $\{(2,4),(1,3)\}$ 的权值为 $4$。不存在权值大于 $4$ 的匹配,所以这是一个最大权最大匹配。其他可接受的输出还有:

2 3
1 4

3
1 2
2 3

1 3

在 $T$ 中,顶点 $1$ 与 $3$ 的距离为 $2$,因此匹配 $\{(1,3)\}$ 的权值为 $2$。不存在权值大于 $2$ 的匹配,所以这是一个最大权最大匹配。另一个可接受的输出是:

3 1

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le u_i \lt v_i \le N$
• 输入的图是一棵树。
• 所有输入值均为整数。

提示

答案不唯一,输出任意合法解即可。