102702: [AtCoder]ABC270 C - Simple path
Description
Score : $300$ points
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.
Input
题意翻译
给定一个树，求这个树上两个点的简单路径。请按照 $x,a,b,c,\cdots,y$ 的顺序输出。（输入的两个点的顺序是 $x$，$y$）Output
问题描述
有一个有$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$的简单路径。限制条件
- $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$
- 输入中的所有值都是整数。
- 给定的图是一棵树。
输入
输入是通过标准输入给出的，格式如下：
$N$ $X$ $Y$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$
输出
按照顺序打印出从顶点$X$到顶点$Y$的简单路径上的所有顶点，顶点之间用空格隔开。
样例输入1
5 2 5 1 2 1 3 3 4 3 5
样例输出1
2 1 3 5
树$T$如下所示。从顶点$2$到顶点$5$的简单路径是$2$ $\to$ $1$ $\to$ $3$ $\to$ $5$。
因此，应该按照这个顺序打印$2,1,3,5$，顶点之间用空格隔开。
样例输入2
6 1 2 3 1 2 5 1 2 4 1 2 6
样例输出2
1 2
树$T$如下所示。