はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるLCA問題まとめ [auxiliary tree]

LCA

  • Lowest Common Ancestor
  • 根付き木のある2頂点u,vの共通祖先で最も根から遠い頂点を高速に見つけること
  • yukicoder上でのantaさんの解説
  • アルゴリズムはいくつかある「ダブリング」「HL分解」「RMQ使用」RMQが最速っぽいけど、体感HL分解の方が早いような…
  • LCA+根からある頂点への情報(深さとかコスト和とか)を使う解法が多い

例) 頂点aから頂点bへの距離はdist(根,a) + dist(根,b) - 2*dist(根,lca(a,b))となる

  • LCAは単体では余り使われないので、これだけ知っててもしょうがなかったりするが、無いと解けない問題はある
  • 根が変わる場合のLCA

【発展的話題】LCA

  • LCA木、auxiliary tree
    • 木のある頂点集合から、その集合とそのLCAからなる頂点集合を得る方法がある
    • 木のある頂点集合の個数がKであれば、O(K)で構築でき、得られる頂点集合の個数もO(K)
  • 構築方法

1. dfsで木の頂点をpre-orderで番号付けする(オイラーツアー)
2. 木のある頂点集合をpre-order昇順でソート
3. 隣接する2頂点についてLCAを取って、それを頂点集合に追加する
4. (辺も構築するなら)追加された頂点も含めて、再度pre-order昇順でソートし、隣接する頂点(i,i+1)でLCAを取ると、LCAとi+1の間に辺を作れる