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
問題
AOJ Lowest Common Ancestor
ABC014 D.閉路
yukicoder No.898 tri-βutree 解説
yukicoder No.386 貪欲な領主
yukicoder No.901 K-ary εxtrεεmε 解説
JOI 国のお祭り事情 見応えのある解説
HR Bananas Multiplier (Hard)
【発展的話題】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の間に辺を作れる