AT_abc213_d [ABC213D] Takahashi Tour

题目描述

在 AtCoder 国，有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $N-1$ 条道路，编号为 $1$ 到 $N-1$。
通过第 $i$ 条道路，可以在城市 $A_i$ 和城市 $B_i$ 之间双向移动。保证所有城市之间都可以通过道路互相到达。

高桥君从城市 $1$ 出发，按照以下规则进行旅行：

• 如果当前所在城市与之直接相连的城市中，存在尚未访问过的城市，则前往这些城市中编号最小的城市。
• 如果不存在这样的城市：
  • 如果当前城市是城市 $1$，则结束旅行。
  • 否则，返回到第一次到达当前城市时所处的前一个城市。

请按顺序输出高桥君在旅行过程中访问的城市，包括旅行开始和结束时的城市 $1$。

输入格式

输入以如下格式从标准输入读入：

$N$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$

输出格式

请按顺序输出高桥君访问的城市编号（包括旅行开始和结束时的城市 $1$），用空格分隔。

输入输出样例 #1

输入 #1

4
1 2
4 2
3 1

输出 #1

1 2 4 2 1 3 1

输入输出样例 #2

输入 #2

5
1 2
1 3
1 4
1 5

输出 #2

1 2 1 3 1 4 1 5 1

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• 保证所有城市之间都可以通过道路互相到达

样例解释 1

高桥君的旅行过程如下：

• 最初在城市 $1$。
• 与城市 $1$ 直接相连且未访问的城市有 $2, 3$，选择编号最小的城市 $2$ 前往。
• 与城市 $2$ 直接相连且未访问的城市有 $4$，前往城市 $4$。
• 与城市 $4$ 直接相连且未访问的城市没有，返回到上一次在城市 $4$ 前所处的城市 $2$。
• 与城市 $2$ 直接相连且未访问的城市没有，返回到上一次在城市 $2$ 前所处的城市 $1$。
• 与城市 $1$ 直接相连且未访问的城市有 $3$，前往城市 $3$。
• 与城市 $3$ 直接相连且未访问的城市没有，返回到上一次在城市 $3$ 前所处的城市 $1$。
• 与城市 $1$ 直接相连且未访问的城市没有，旅行结束。

由 ChatGPT 4.1 翻译