解説 | Balanced Path

解説

頂点 $S$ を根として DFS 木を構築することを考える。

無向グラフの DFS 木では、祖先・子孫の関係にない頂点間に辺は存在しない。根からのパスに含まれる頂点をすべて削除すると、残った連結成分はそれぞれ、パス上の頂点から分かれる部分木となる。

よって、DFS 木の各頂点 $v$ について、 $v$ を根とする部分木の頂点数を $sz_v$ とすると、以下のように頂点を追加することによって構築したパスが条件を満たす。

頂点 $S$ を始点として追加する。
現在の最後に追加した頂点 $v$ の子のうち、 $sz_u \gt \left\lfloor \dfrac{N}{2}\right\rfloor$ を満たす頂点 $u$ が存在すれば、 $u$ を追加する。
そのような子が存在しなければ終了する。あれば1 に戻る。

部分木の頂点数が $\left\lfloor \dfrac{N}{2}\right\rfloor$ を超える子は高々 $1$ 個であるため、パスから分岐する部分木の頂点数はいずれも $\left\lfloor \dfrac{N}{2}\right\rfloor$ 以下となる。

よって、構築したパスは条件を満たし、答えは常に存在する。

よって、 $O(N+M)$ でこの問題を解くことができる。