最小共通祖先

[Lowest Common Ancestor] 木の頂点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：Lowest Common Ancestor）を求めるアルゴリズム | アルゴリズムロジック

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

LCA ダブリング

オイラーツアー スパーステーブル https://ikatakos.com/pot/programming_algorithm/graph_theory/lowest_common_ancestor

ABC014D