E - Farthest Vertex https://atcoder.jp/contests/abc428/tasks/abc428_e

abc428_e.py

from collections import deque


def bfs(v):
    dist = [-1] * N
    dist[v] = 0
    que = deque([v])
    while que:
        v = que.popleft()
        for u in T[v]:
            if dist[u] >= 0:
                continue
            dist[u] = dist[v] + 1
            que.append(u)
    return dist


def farthest_vertex(dist):
    u, m = 0, dist[0]
    for i in range(1, N):
        if m <= dist[i]:
            m = dist[i]
            u = i
    return u


N = int(input())
T = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    T[a].append(b)
    T[b].append(a)

# 頂点0から各頂点までの距離を求め、一番遠い点をuとする
dist_0 = bfs(0)
u = farthest_vertex(dist_0)

# 頂点uから各頂点までの距離を求め、一番遠い点をvとする
dist_u = bfs(u)
v = farthest_vertex(dist_u)

# 頂点vから各頂点までの距離を求める
dist_v = bfs(v)
for i in range(N):
    if dist_u[i] > dist_v[i]:
        print(u + 1)
    elif dist_u[i] < dist_v[i]:
        print(v + 1)
    else:
        print(max(u + 1, v + 1))