C - Simple path
当前没有测试数据。
C - Simple path
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:
Output
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
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.
6 1 2
3 1
2 5
1 2
4 1
2 6
1 2
The tree $T$ is shown below.
