/ 
Time Limit: 2 sec / Memory Limit: 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, N が M に現れる回数がたかだか 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