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}$

输入输出样例 #1

输入 #1

4
1 2
2 3
3 4

输出 #1

2 4
1 3

输入输出样例 #2

输入 #2

3
1 2
2 3

输出 #2

1 3

说明/提示

数据范围

• $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 翻译