← 返回题目列表

AtCoder · abc270_c

F. 简单路径

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有一棵树 T 与 N 顶点。的 i第边缘 (1\leq i\leq N-1) 连接顶点 U_i 和顶点 V_i.

给你两个不同的顶点 X 和 Y in T。 列出从顶点开始的简单路径上的所有顶点 X 到顶点 Y 按顺序,包括端点。

可以证明,对于任意两个不同的顶点 a 和 b 在树中,有一条唯一的简单路径 a to b.

什么是简单路径? 对于顶点 图表中的 X 和 Y 在图表中 G,一个 路径 从顶点 X 到顶点 Y 是一系列顶点 v_1,v_2, \ldots, v_k 这样 v_1=X, v_k=Y,和 v_i 和 v_{i+1} 由每个边缘连接 1\leq i\leq k-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 is 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 如下所示。