Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 270 C問題 Simple Path

AtCoder ABC270 ABC C問題 300 pts

問題

提出解答

問題の概要

$N$ 頂点からなる木 $T=(V,E)$ が与えられる.

$E:=\{1,2, \dots, N\}$
$V:=\{U_j V_j \mid j=1,2, \dots, N-1\}$

このとき, $T$ 上の頂点 $X$ を始点, 頂点 $Y$ を終点とする (単純) パスを求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq X,Y \leq N$
$1 \leq U_j, V_j \leq N$
$T$ は木である.

解法

グラフ上のパスを求める問題なので, DFS や BFS をそのまま実装すればよい. また, 木におけるパスは唯一であることから, DFS や BFS で求められたパスをそのまま出力すれば良い.