AT_abc270_c [ABC270C] Simple path

题目描述

有一棵包含 $N$ 个顶点的树 $T$，第 $i$ 条边（$1\leq i\leq N-1$）连接顶点 $U_i$ 和顶点 $V_i$。

给定树 $T$ 上两个不同的顶点 $X$ 和 $Y$，请依次输出从顶点 $X$ 到顶点 $Y$ 的简单路径上的所有顶点（包括端点）。

可以证明，对于树上任意两个不同的顶点 $a,b$，从 $a$ 到 $b$ 的简单路径唯一。

什么是简单路径？
对于图 $G$ 上的顶点 $X,Y$，如果存在一个顶点序列 $v_1,v_2,\ldots,v_k$，满足 $v_1=X$，$v_k=Y$，并且对于所有 $1\leq i\leq k-1$，$v_i$ 和 $v_{i+1}$ 之间有一条边，则称该序列为从顶点 $X$ 到顶点 $Y$ 的路径。
如果 $v_1,v_2,\ldots,v_k$ 中所有顶点都互不相同，则称该路径为从顶点 $X$ 到顶点 $Y$ 的简单路径。

输入格式

输入以以下格式从标准输入读入。

$N$ $X$ $Y$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

输出格式

请按顺序输出从顶点 $X$ 到顶点 $Y$ 的简单路径上的所有顶点编号，编号之间用空格分隔。

输入输出样例 #1

输入 #1

5 2 5
1 2
1 3
3 4
3 5

输出 #1

2 1 3 5

输入输出样例 #2

输入 #2

6 1 2
3 1
2 5
1 2
4 1
2 6

输出 #2

1 2

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $1\leq X,Y\leq N$
• $X\neq Y$
• $1\leq U_i,V_i\leq N$
• 所有输入均为整数
• 给定的图为树

样例解释 1

树 $T$ 如下图所示，从顶点 $2$ 到顶点 $5$ 的简单路径为 $2 \to 1 \to 3 \to 5$。因此，输出 $2,1,3,5$，并用空格分隔。

样例解释 2

树 $T$ 如下图所示。

由 ChatGPT 4.1 翻译