Score : $300$ points

问题描述

存在一棵包含 $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$，从顶点 $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}$ 由一条边相连。另外，如果 $v_1, v_2, \ldots, v_k$ 全部不相同，则称这条路径是从顶点 $X$ 到顶点 $Y$ 的简单路径。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a tree $T$ with $N$ vertices. The $i$-th edge $(1\leq i\leq N-1)$ connects vertex $U_i$ and vertex $V_i$.

You are given two different vertices $X$ and $Y$ in $T$. List all vertices along the simple path from vertex $X$ to vertex $Y$ in order, including endpoints.

It can be proved that, for any two different vertices $a$ and $b$ in a tree, there is a unique simple path from $a$ to $b$.

What is a simple path? For vertices $X$ and $Y$ in a graph $G$, a path from vertex $X$ to vertex $Y$ is a sequence of vertices $v_1,v_2, \ldots, v_k$ such that $v_1=X$, $v_k=Y$, and $v_i$ and $v_{i+1}$ are connected by an edge for each $1\leq i\leq k-1$. Additionally, if all of $v_1,v_2, \ldots, v_k$ are distinct, the path is said to be a simple path from vertex $X$ to vertex $Y$.

Constraints

• $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$
• All values in the input are integers.
• The given graph is a tree.

Input

The input is given from Standard Input in the following format:

$N$ $X$ $Y$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_{N-1}$ $V_{N-1}$

Output

Print the indices of all vertices along the simple path from vertex $X$ to vertex $Y$ in order, with spaces in between.

Sample Input 1

5 2 5
1 2
1 3
3 4
3 5

Sample Output 1

2 1 3 5

The tree $T$ is shown below. The simple path from vertex $2$ to vertex $5$ is $2$ $\to$ $1$ $\to$ $3$ $\to$ $5$.
Thus, $2,1,3,5$ should be printed in this order, with spaces in between.

Sample Input 2

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

Sample Output 2

1 2

The tree $T$ is shown below.

update @ 2024/3/10 11:23:14