4243: Simple path

# Simple path ### 内存 1024MB ### 时间 2S ## 题目描述 在一个有 $N$ 个顶点的树 $T$ 中，第 $i$ 条边 $(1≤i≤N-1)$ 连接顶点$U_i$ 和顶点 $V_i$。给定两个不同的顶点 $X$ 和 $Y$，请按顺序列出从顶点 $X$ 到顶点 $Y$ 的简单路径上的所有顶点，包括端点。注意，对于树中任意两个不同的顶点 $a$ 和 $b$，从 $a$ 到 $b$ 的简单路径是唯一的。 什么是简单路径(Simple Path)？ 在图 $ G $ 中，对于顶点 $ X $ 和 $ Y $，如果存在一个顶点序列 $ v_1, v_2, \ldots, v_k $ 满足以下条件，则称其为从顶点 $ X $ 到顶点 $ Y $ 的**路径**： - $ 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 $ 的**简单路径**。 ## 输入格式 输入从标准输入中按以下格式给出： $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 ``` ### 输入样例2 ``` 6 1 2 3 1 2 5 1 2 4 1 2 6 ``` ### 输出样例2 ``` 1 2 ``` ## 数据范围与提示 【样例1说明】 树 $T$ 如下图所示。从顶点 2 到顶点 5 的简单路径是 2 → 1 → 3 → 5。 因此，应按此顺序输出 2, 1, 3, 5，中间用空格分隔。  【样例2说明】 树 $T$ 如下图所示。  【数据范围】 $1 ≤ N ≤ 2 × 10^5$ $1 ≤ X, Y ≤ N$ $X ≠ Y$ $1 ≤ U_i, V_i ≤ N$，输入中的所有值都是整数。给定的图是一棵树。 ## 题目来源 ABC270C