← 返回题目列表

AtCoder · abc362_f

I. 树上的完美搭配

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

你得到了一棵树 T 与 N 顶点。顶点已编号 1 to N,以及 i第边缘 (1 \leq i \leq N-1) 连接顶点 u_i 和 v_i 双向。

使用 T,定义一个完整的图 G 与 N 顶点如下:

  • 重量 顶点之间的边的 w(x,y) 顶点之间的边 x 和 y in G 是顶点之间的最短距离 x 和 y in T.

找到一个 最大重量最大匹配 in 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) 已最大化。

约束

  • 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

In T,顶点之间的距离 2 和 4 is 2,以及顶点之间的距离 1 和 3 is 2,所以匹配的权重 \{(2,4),(1,3)\} is 4。没有权重大于的匹配 4,所以这是最大权重最大匹配。其他可接受的输出包括:

2 3
1 4

示例输入 2

3
1 2
2 3

示例输出 2

1 3

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

3 1