AtCoder Beginner Contest 213 [ D - Takahashi Tour ] https://atcoder.jp/contests/abc213/tasks/abc213_d

abc213_d.py

'''
[問題]
https://atcoder.jp/contests/abc213/tasks/abc213_d

[結果]
PyPy3(7.3.0) AC 1169ms
Python(3.8.2) AC 1151ms
'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

N = int(input())

route = [set() for _ in range(N)]

trip = []

for _ in range(N-1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    route[A].add(B)
    route[B].add(A)

for i in range(N):
    route[i] = sorted(route[i])

visit = [0] * N
visit[0] = -1   # 0を訪問済みにしとく。必要ないか？

# Depth First Searchで深さを計算する
def dfs(x):

    trip.append(x+1)

    for to in route[x]:
        if visit[to] == 0:
            visit[to] = (x + 1)
            dfs(to)
            # 木構造の戻りは、問題の前提から戻るに決まってるので、追加しとくのがポイント！
            # 片道で済むので計算量が下がる
            trip.append(x + 1)

    # 行くとこ無かったらDFSで戻る処理
    # これやっちゃうと、計算量多すぎ。
    # 問題の前提から、木構造は戻るに決まってるから一番下まで行ったら終わりで良い
    '''
    if x:
        dfs(visit[x] - 1)
    '''

dfs(0)

# listを横一列に表示
print(*trip)