103625: [Atcoder]ABC362 F - Perfect Matching on a Tree

Problem Statement

You are given a tree $T$ with $N$ vertices. The vertices are numbered $1$ to $N$, and the $i$-th edge $(1 \leq i \leq N-1)$ connects vertices $u_i$ and $v_i$ bidirectionally.

Using $T$, define a complete graph $G$ with $N$ vertices as follows:

• The weight $w(x,y)$ of the edge between vertices $x$ and $y$ in $G$ is the shortest distance between vertices $x$ and $y$ in $T$.

Find one maximum weight maximum matching in $G$. That is, find a set of $\lfloor N/2 \rfloor$ pairs of vertices $M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\}$ such that each vertex $1,2,\dots, N$ appears in $M$ at most once, and $\displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i)$ is maximized.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N$
• The input graph is a tree.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print a solution as $\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\}$ in the following format. If multiple solutions exist, any of them is acceptable.

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

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2 4
1 3

In $T$, the distance between vertices $2$ and $4$ is $1$, and the distance between vertices $1$ and $3$ is $2$, so the weight of the matching $\{(2,4),(1,3)\}$ is $3$. There is no matching with a weight greater than $3$, so this is a maximum weight maximum matching. Other acceptable outputs include:

3 4
2 1

and

1 3
2 4

Sample Input 2

3
1 2
2 3

Sample Output 2

1 3

In $T$, the distance between vertices $1$ and $3$ is $2$, so the weight of the matching $\{(1,3)\}$ is $2$. There is no matching with a weight greater than $2$, so this is a maximum weight maximum matching. Another acceptable output is:

3 1

问题陈述

给你一个有N个顶点的树T。顶点编号为1到N，第i条边（1≤i≤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),…,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})}，使得每个顶点1,2,…, N在M中最多出现一次，并且$\displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i)$最大化。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N$
• 输入的图是一棵树。
• 所有输入值都是整数。

输入

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

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

示例输入1

4
1 2
2 3
3 4

示例输出1

2 4
1 3

在T中，顶点2和4之间的距离是1，顶点1和3之间的距离是2，所以匹配$\{(2,4),(1,3)\}$的权重是3。没有权重大于3的匹配，所以这是一个最大权重最大匹配。其他可接受的输出包括：

3 4
2 1

以及

1 3
2 4

示例输入2

3
1 2
2 3

示例输出2

1 3

在T中，顶点1和3之间的距离是2，所以匹配$\{(1,3)\}$的权重是2。没有权重大于2的匹配，所以这是一个最大权重最大匹配。另一个可接受的输出是：

3 1