AT_abc270_c.[ABC270C] Simple path

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵包含 $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$ ，如果存在一个顶点序列 $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$ 的简单路径。

输入格式

输入以以下格式从标准输入读入。

$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\leq N\leq 2\times 10^5$
$1\leq X,Y\leq N$
$X\neq Y$
$1\leq U_i,V_i\leq N$
所有输入均为整数
给定的图为树

样例解释 1

树 $T$ 如下图所示，从顶点 $2$ 到顶点 $5$ 的简单路径为 $2 \to 1 \to 3 \to 5$ 。因此，输出 $2,1,3,5$ ，并用空格分隔。

样例解释 2

树 $T$ 如下图所示。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页