F - Perfect Matching on a Tree 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 550

問題文

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, NM に現れる回数がたかだか 1 回であるようなもののうち、 \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 間の距離は 2、頂点 1,3 間の距離は 2 なので、マッチング \{(2,4),(1,3)\} の重みは 4 です。重みが 4 より大きいマッチングは存在しないので、これが最大重み最大マッチングの一つです。他にも、

2 3
1 4

などを出力しても正解になります。


入力例 2

3
1 2
2 3

出力例 2

1 3

T において、頂点 1,3 間の距離は 2 なので、マッチング \{(1,3)\} の重みは 2 です。重みが 2 より大きいマッチングは存在しないので、これが最大重み最大マッチングの一つです。他にも、

3 1

を出力しても正解になります。

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 2, and the distance between vertices 1 and 3 is 2, so the weight of the matching \{(2,4),(1,3)\} is 4. There is no matching with a weight greater than 4, so this is a maximum weight maximum matching. Other acceptable outputs include:

2 3
1 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