ancestor query・LCA

概要

根付き木の祖先関係を時刻またはbinary liftingで索引化し、LCAと木上距離を答える。

考え方

二頂点の深さを揃え、上位から同じ祖先へ近づけることでLCAを求める。binary liftingでは2^k上の祖先を保存し、同時に飛び越えてよい区間を判定する。

根rの親をrとしてup[0][v]=parent[v]、up[k+1][v]=up[k][up[k][v]]を作る。level ancestorは必要回数hを二進分解してupを適用し、h>depth[v]なら存在しないと返す。

LCA(u,v)は深い方を深さ差だけ上げる。一致したらその頂点。違えばkを大きい方から見て、up[k][u]≠up[k][v]のときだけ両方を飛ばす。共通祖先へ飛び越えず、それぞれがLCAの異なる子の側に留まる。最後は両親が一致するのでup[0][u]がLCAとなる。rootDistを根からの辺長和として保存すれば距離はrootDist[u]+rootDist[v]−2rootDist[LCA]。

成立条件と計算量

O(N log N)前処理・空間、O(log N)query。Euler tourとRMQなら別の時間・空間 tradeoffになる。根の祖先、祖先同士のquery、kが深さを超える場合を明示する。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。深さ調整とbinary liftingを用い、LCA・祖先・距離のqueryを処理する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 木のancestor・部分木・pathを索引化する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-tree-ancestor-lca

ancestor query・LCA

習得する技能

  • binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: doubling・binary lifting。

このUnitを直接前提とする単元: Heavy-Light Decomposition、virtual tree・auxiliary tree。

doubling・binary liftingで得た考え方と実装を再利用し、ancestor query・LCAの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • ancestor query・LCAの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠