分数: 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