Lowest Common Ancestor(LCA)

木の頂点a,bが与えられた時に、両方の祖先である頂点のうち最も深さが深いもの

求め方

親へのポインタが与えられてる時のダブリング

前処理

各頂点から子へのポインタを作る

DFSで各頂点の深さを求める

親へのポインタをダブリングして2^i個上の頂点を得る(O(NlogN))

クエリ

与えられた2頂点の深さを得る

深い方のいくつか上の頂点を選び高さを揃える

n個上の親が同じものになる最小のnを二分探索で求める

備考

n個上の親を得る処理はO(logN)だが、二分探索の時は上の方から試していけば全体でO((logN)^2)→O(logN)にできる

高々20倍の高速化なのでやらないでいいかなと思ったがこれをやらないとTLEになってしまった。

AOJ GRL_5_C https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C

---

グラフが与えられるパターンと親頂点が与えられるパターン

LCA ダブリング

オイラーツアー スパーステーブル