Simple path

题目描述

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$. 列出从顶点 $X$ 到顶点 $Y$ 的简单路径上的所有顶点，按顺序，包括端点。 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$.

输入格式

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}$

输出格式

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

5 2 5
1 2
1 3
3 4
3 5

2 1 3 5

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

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

标签: AtCoder|abc270C

来源

AtCoder|abc270C