Perfect Matching on a Tree

题目描述

给定一棵有 $N$ 个顶点的树 $T$。顶点编号为 $1$ 到 $N$，第 $i$ 条边 $(1 \leq i \leq 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

2 3
1 4

3
1 2
2 3

1 3

3 1

提示

$2 \leq N \leq 2 \times 10^5$ 1 \leq u_i < v_i \leq N 输入的图是棵树。 所有输入值均为整数。在 $T$ 中，顶点 $2$ 和 $4$ 之间的距离是 $2$，顶点 $1$ 和 $3$ 之间的距离是 $2$，所以匹配 $\{(2,4),(1,3)\}$ 的权值为 $4$。不存在权值大于 $4$ 的匹配，因此这是一个最大权最大匹配。其他可接受的输出包括：
在 $T$ 中，顶点 $1$ 和 $3$ 之间的距离是 $2$，所以匹配 $\{(1,3)\}$ 的权值为 $2$。不存在权值大于 $2$ 的匹配，因此这是一个最大权最大匹配。另一个可接受的输出是：

标签: AtCoder|abc362F

来源

AtCoder|abc362F