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が深さを超える場合を明示する。
問題一覧
- ABC298 Ex「Sum of Min of Length」 公式問題組合せ: 根付き木DP・部分木集約
技能・出典
主題: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。主タグ: ancestor query・LCA / 補助タグ: 根付き木DP・部分木集約
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC267 F「Exactly K Steps」 公式問題
技能・出典
主題: 基準点からの木距離・剰余類・直径・中心(一回または二回の木探索で少数の基準点からの距離を求め、一意経路・直径端点・中心の性質から頂点分類や最遠距離条件を整理できる。)。既習技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。主タグ: 木距離・直径・中心・最遠点 / 補助タグ: ancestor query・LCA
- ABC294 G「Distance Queries on a Tree」 公式問題主題: Euler順による部分木区間化
技能・出典
主題: Euler順による部分木区間化(Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。)。追加で学ぶ技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: ancestor query・LCA、Euler順による部分木区間化 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC329 G「Delivery on Tree」 公式問題主題: 根付き木DP・部分木集約
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: ancestor query・LCA
- ABC405 F「Chord Crossing」 公式問題主題: laminar区間族の包含木構築
技能・出典
主題: laminar区間族の包含木構築(laminar区間の開閉端点をstackで処理し、直接包含関係と各点の最小包含区間を木として構築して、包含差分を木上pathへ変換できる。)。既習技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。) / 円環順序・chord交差(円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。)。主タグ: laminar区間族の包含木構築 / 補助タグ: 円環順序・chord交差、ancestor query・LCA
- ABC438 F「Sum of Mex」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 根付き木DP・部分木集約、ancestor query・LCA
- ABC460 F「Farthest Pair Query」 公式問題主題: 区間monoid要約
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。) / 基準点からの木距離・剰余類・直径・中心(一回または二回の木探索で少数の基準点からの距離を求め、一意経路・直径端点・中心の性質から頂点分類や最遠距離条件を整理できる。)。主タグ: 区間monoid要約 / 補助タグ: ancestor query・LCA、木距離・直径・中心・最遠点
前提・学習成果・出典
習得対象の目安: 水色(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の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。