← 返回题目列表

AtCoder · abc428_e

H. 最远顶点

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

分数: 475 点

问题陈述

有一棵树 N 顶点编号 1 to 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