103625: [Atcoder]ABC362 F - Perfect Matching on a Tree
Description
Score : $550$ points
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
Output
得分:550分
问题陈述
给你一个有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