AOJ 2170 - Problem F: Marked Ancestor

問題リンク

人々はおすすめするような素晴らしい問題らしいが、こういうのはクエリ平方分割で常勝ｗ！

解説

クエリ平方分割をします。

クエリがバケットサイズを超えたら、多始点BFSの要領で更新していきます(深いほうのみに潜っていくようにしましょう)

残ってる分に関しては、オイラーツアーなどでで部分木判定をして、深さと比較しながらやりましょう。

計算量はです。

オンラインで解けているのも魅力ですね

提出コード

onlinejudge.u-aizu.ac.jp