提出 #29831782

---

ソースコード 拡げる

n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

num_leaf = 0
l = [1e9] * (n + 1)
r = [0] * (n + 1)

stack = [(~1, 0), (1, 0)]
while stack:
    curr, prev = stack.pop()
    if curr > 0:
        if graph[curr] == [prev]:
            num_leaf += 1
            l[curr] = num_leaf
            r[curr] = num_leaf
        else:
            stack.append([~curr, None])
            for next_v in graph[curr]:
                if next_v == prev:
                    continue
                stack.append([next_v, curr])

    else:
        curr = ~curr
        for child_v in graph[curr]:
            l[curr] = min(l[curr], l[child_v])
            r[curr] = max(r[curr], r[child_v])

for i in range(1, n + 1):
    print(l[i], r[i])

提出情報

ジャッジ結果