Kazun の競プロ記録

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

AtCoder Beginner Contest 225 B 問題 Star or Not

AtCoder ABC ABC225 B問題 200 pts

問題

提出解答

問題の概要

$N$ 頂点の木 $T$ が与えられる. $i$ 番目の辺は頂点 $a_i, b_i$ を結んでいる. $T$ はスターか?

制約

$3 \leq N \leq 2 \times 10^5$
$1 \leq a_i, b_i \leq N$
$T$ は木

解法

頂点 $v$ の次数を $\operatorname{deg}(v)$ と書くことにする. このとき, $T$ がスターであることと, $\operatorname{deg}(v)=N-1$ なる頂点 $v$ が存在することは同値である.

よって, $T$ の次数を記録し, 次数が $N-1$ の頂点が存在するかどうかをみればよい.