AT_abc362_f [ABC362F] Perfect Matching on a Tree

给定一棵有 $N$ 个顶点的树 $T$。$T$ 的顶点编号为 $1$ 到 $N$，第 $i$ 条边（$1 \leq i \leq N-1$）连接顶点 $u_i$ 和顶点 $v_i$，且为双向边。 利用 $T$，定义一个 $N$ 个顶点的完全图 $G$，具体如下： - $G$ 中顶点 $x$ 与顶点 $y$ 之间的边的权值 $w(x, y)$ 定义为 $T$ 中顶点 $x$ 与顶点 $y$ 之间的最短距离。 请在 $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$ 中出现次数至多 $1$ 次，并且 $\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}$

请输出一个满足条件的匹配 $M = \{(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}$

### 数据范围 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq u_i < v_i \leq N$ - 输入的图保证是一棵树 - 所有输入均为整数 ### 样例解释 1 在 $T$ 中，顶点 $2$ 和 $4$ 之间的距离为 $2$，顶点 $1$ 和 $3$ 之间的距离为 $2$，因此匹配 $\{(2,4),(1,3)\}$ 的权值为 $4$。不存在权值大于 $4$ 的匹配，因此这是最大权值最大匹配之一。你也可以输出 `2 3 1 4` 等其它答案。 ### 样例解释 2 在 $T$ 中，顶点 $1$ 和 $3$ 之间的距离为 $2$，因此匹配 $\{(1,3)\}$ 的权值为 $2$。不存在权值大于 $2$ 的匹配，因此这是最大权值最大匹配之一。你也可以输出 `3 1` 等其它答案。 由 ChatGPT 4.1 翻译