技術室奥プログラミングコンテスト#4 Day2：B - Stalker

問題
解法
解答

問題

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_b

解法

問題を整理すると，写真がある頂点は 1 つの枝分かれしない直線状のパス上にあるかどうかを判定する問題になる．

適当な頂点を根として DFS をする．DFS のときに「今いる頂点までで写真がある頂点があったか」（flag とする）という情報を持たせておく．そして，今いる頂点の子の部分木の中で写真が含まれている部分木がいくつあるか（k とする）を求める．もし，flag && k >= 2 あるいは !flag && k >= 3 であるような頂点が 1 つでも存在したとき，写真がある頂点同士を結ぶパスがその頂点で枝分かれしてしまっていることを意味するので，答えは "trumpet" となる．逆にこのような頂点が存在しなければ，答えは "Yes" となる．O(N + M)．