/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 頂点の木 T があり、 i (1\leq i\leq N-1) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。
T 上の相異なる 2 頂点 X,Y が与えられるので、 頂点 X から頂点 Y への単純パス上の頂点（端点含む）を順に列挙してください。
ただし、木上の任意の相異なる 2 頂点 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 への 単純パス と呼びます。制約
- 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 は以下のような形です。
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.