E - Farthest Vertex Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

頂点に 1 から N の番号がついた N 頂点の木があります。i 番目の辺は頂点 A_i と頂点 B_i を結ぶ辺です。
頂点 u と頂点 v の距離を、頂点 u と頂点 v を両端点とするパスに含まれる辺の本数として定義します。(このパスは一意に定まります)

v = 1, 2, \dots, N について次の問題を解いてください。

  • 頂点 1, 2, \dots, N のうち頂点 v からの距離が最大となる頂点の番号を出力してください。ただし、条件を満たす頂点が複数存在する場合は 最も番号が大きい頂点 を出力してください。

制約

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \lt B_i \leq N
  • 入力で与えられるグラフは木
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

N 行出力せよ。i 行目には v=i の時の答えを出力せよ。

入力例 1

3
1 2
2 3

出力例 1

3
3
1

頂点 1 からの距離が最大となる点は頂点 3 です。
頂点 2 からの距離が最大となる点は頂点 1 および頂点 3 です。このうち番号が大きい頂点である頂点 3 が答えとなります。
頂点 3 からの距離が最大となる点は頂点 1 です。

入力例 2

5
1 2
2 3
2 4
1 5

出力例 2

4
5
5
5
4

Score : 475 points

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.
Define the distance between vertices u and v as the number of edges in the path with endpoints at vertices u and v. (This path is uniquely determined.)

Solve the following problem for v = 1, 2, \dots, N.

  • Among vertices 1, 2, \dots, N, output the number of the vertex that has the maximum distance from vertex v. If there are multiple vertices that satisfy the condition, output the vertex with the largest number.

Constraints

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \lt B_i \leq N
  • The graph given in the input is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Output N lines. The i-th line should contain the answer for v=i.

Sample Input 1

3
1 2
2 3

Sample Output 1

3
3
1

The vertex with the maximum distance from vertex 1 is vertex 3.
The vertices with the maximum distance from vertex 2 are vertices 1 and 3. Among them, vertex 3, which has the larger number, is the answer.
The vertex with the maximum distance from vertex 3 is vertex 1.

Sample Input 2

5
1 2
2 3
2 4
1 5

Sample Output 2

4
5
5
5
4