URAL 1056 Computer Net

나무 위의 임의의 점에서 가장 멀리 떨어진 점은 아버지의 노드에서 왔거나 아들의 노드에서 왔다.따라서 먼저 아래에서 위로 dp를 한 번 진행하여 아들 노드에서 오는 가장 먼 거리를 처리할 수 있다.그리고 위에서 아래로 dp를 한 번 더 진행하고 아버지의 노드에서 올 때 가장 먼 거리를 전달한다. 이렇게 하면 아들의 노드에서 오는 가장 먼 거리와 비교하면 이 점에서 가장 먼 거리를 찾을 수 있다.

INF = 0x3f3f3f3f
N = 0
g = [[]]
dp = []
ans = []
res = 0

def input():
    global N, g
    N = int(raw_input())
    g = [[] for i in range(N + 1)]
    for i in range(2, N + 1):
        x = int(raw_input())
        g[x].append(i), g[i].append(x)

def bottom_up(x, px):
    global dp, g
    dp[x] = 0
    for y in g[x]:
        if y == px: continue
        bottom_up(y, x)
        dp[x] = max(dp[x], dp[y] + 1)

def top_down(x, px, dis):
    global dp, res, ans, g
    t = max(dp[x], dis)
    if t < res:
        res = t
        ans = [x]
    elif t == res: ans.append(x)
    opt = [dp[i] + 1 for i in g[x]]
    for i in range(len(opt) - 2, -1, -1):
        opt[i] = max(opt[i], opt[i + 1])
    i = 0
    t = dis
    for y in g[x]:
        i += 1
        if y == px: continue
        ndis = t
        if i < len(opt) and opt[i] > ndis: ndis = opt[i]
        top_down(y, x, ndis + 1)
        t = max(t, dp[y] + 1) 

def process():
    global N, dp, res, ans
    dp = [-1 for i in range(N + 1)]
    bottom_up(1, -1)
    res = 0x3f3f3f3f
    top_down(1, -1, 0)
    ans.sort()
    for i in ans: print i,
    print

#main
input()
process()