木のancestor・部分木・pathを索引化する

概要

木の上で繰り返し調べたいものは、ある頂点の子孫全体だろうか、二頂点を結ぶ経路だろうか、それとも少数の指定点を結ぶ枝分かれだろうか。必要な集合や順序を配列・祖先表・小さな木へ写すと、毎回木全体を探索せずに処理できる。何を保存したいかを先に決め、対応する下位単元を選ぶ。包含関係を木に変換する方法は独立した節で学ぶ。

考え方

部分木の集合を、一つの区間にする

木の集約と同じ、辺が r–a,a–b,r–cr\text{–}a,a\text{–}b,r\text{–}c の4頂点木を使う。各辺の長さは1、根は rr とする。DFSで aa 側を先に訪ね、頂点へ初めて入った順だけを並べると (r,a,b,c)(r,a,b,c)。添字は0始まりとし、入場時にtinを記録して時計を1増やし、子孫の探索が終わった時点の時計をtoutとする。出場時には時計を増やさない。

頂点tintout部分木の半開区間区間に入る頂点
rr04[0,4)[0,4)r,a,b,cr,a,b,c
aa13[1,3)[1,3)a,ba,b
bb23[2,3)[2,3)bb
cc34[3,4)[3,4)cc

半開区間 [l,h)[l,h) は添字 ll 以上 hh 未満を表す。DFSは一つの部分木へ入ると、その子孫を訪ね終えるまで外へ出ない。そのため、部分木の頂点はちょうどこの区間に並ぶ。頂点の重みをtinの位置へ置けば、aa 側の重みの和は [1,3)[1,3) の区間和になる。辺 r–ar\text{–}a を切った逆側の和も、全体の和から引けば求まる。

「部分木の重みを更新・集計したい」なら、Euler順による部分木区間化から配列の区間処理へ進む。どの頂点を含むかは保存されるが、添字の差は木距離にはならない。例えば r,cr,c の添字の差は3でも距離は1である。

経路の折り返しと、たどる順序を保つ

bb から cc への経路(path)は b→a→r→cb\to a\to r\to c、添字では 2,1,0,32,1,0,3 の順になる。この例では経路の頂点集合が偶然木全体と一致するが、区間 [0,4)[0,4) を左から読んだ順序とは異なる。さらに r→cr\to c の添字は 0,30,3 で、集合としても一つの連続区間にならない。任意の経路を、一つの部分木区間として処理することはできない。

経路はどこで上向きから下向きへ折り返すのか。二頂点の共通祖先のうち最も深い頂点を**最小共通祖先(LCA)**といい、ここでは LCA⁡(b,c)=r\operatorname{LCA}(b,c)=r である。距離が欲しいだけなら、根からの距離を保存し、二頂点の根からの距離の和から、根とLCAの間を二重に数えた分を引けばよい。「何段上の祖先か」「二頂点のLCAや距離は何か」という問いは、ancestor query・LCAへ進む。

一方、経路上の値を更新したり、行列積などを b,a,r,cb,a,r,c の順で合成したりするには、経路自体を扱いたい。Heavy-Light Decomposition(HLD)は、部分木サイズ最大の子への辺を優先して長い鎖を作り、各鎖を配列区間にする。この木では r,a,br,a,b を一つの鎖、cc を別の鎖にでき、b→cb\to c は前者を逆向きにたどる区間と、cc の区間に分かれる。区間内の向きと区間同士の結合順を保てば、経路の順序を復元できる。鎖の外から子へ降りるたび部分木サイズが半分未満になるため、頂点数 NN の木の経路は O(log⁡N)O(\log N) 個の区間で表せる。

経路の和や距離が根からの累積値とLCAだけで求まる場合は、まずその式を検討する。HLDが必要かどうかは、経路上に残る更新・合成の操作から判断する。

指定点を結ぶ枝分かれだけを残す

一照会で指定される頂点が {b,c}\{b,c\} だけなら、二頂点の関係を調べるために全頂点を毎回走査するのはもったいない。しかし b,cb,c だけを残すと、どこで枝が合流するかが消えてしまう。そこでLCAの rr も加え、r→br\to b と r→cr\to c の二辺を張る。前者は元の r→a→br\to a\to b を縮めた長さ2の辺、後者は長さ1の辺である。

virtual tree・auxiliary treeは、このように指定点と必要なLCAを残し、残した頂点間を元の祖先経路に対応する辺で結ぶ。指定点をDFS順に並べ、隣り合う指定点のLCAを追加してから、最も近い残存祖先へつなぐ。指定点が k≥1k\geq1 個なら頂点数は高々 2k−12k-1 個となり、枝分かれを保ったまま小さな木で計算できる。隣接LCAで十分な理由と具体的な接続手順は、子単元で確認する。

保存するのは指定点間の祖先関係と、それを結ぶ経路の構造である。省略された aa の値まで自動的に残るわけではない。距離なら辺長2、経路上の値ならその要約というように、省略部分の寄与を辺へ持たせられるかを確認する。また、追加した rr は指定点ではないので、「指定された頂点の個数」には数えない。

成立条件と計算量

以下では木の形と根を固定し、頂点数を NN、一照会で指定される重複のない頂点数を kk とする。値の更新は扱えても、辺の接続を変える操作には、そのまま同じ索引を使えない。表の費用は定数時間で合成できる値を扱う場合である。

手法前処理の時間・空間一照会の費用
Euler順O(N)O(N)部分木区間の特定 O(1)O(1)
binary liftingO(Nlog⁡N)O(N\log N)祖先・LCA O(log⁡N)O(\log N)
HLDO(N)O(N)経路を O(log⁡N)O(\log N) 個の区間へ分解
virtual treeO(Nlog⁡N)O(N\log N)構築は下記。小木の走査・追加空間は O(k)O(k)

Euler順で区間を特定した後、静的な和は累積和で O(1)O(1)、一点更新・区間和はFenwick Tree等で O(log⁡N)O(\log N)。配列側の準備も、累積和やFenwick Treeの線形構築なら時間・空間とも O(N)O(N) で済む。HLDでは、Segment Treeの構築も時間・空間とも O(N)O(N)、各区間の処理が O(log⁡N)O(\log N) なら経路全体は O(log⁡2N)O(\log^2 N) かかる。

virtual treeは、最初にDFSとbinary liftingを前処理し、一照会では指定点とLCAをソート・接続する。構築時間は

O(klog⁡k+klog⁡N)O(k\log k+k\log N)

となる。小木上で行うDPや、省略経路の要約を得る費用は別途加える。毎回全 NN 頂点分の作業配列を初期化すると、小木へ縮めた利点を失う。

葉の部分木は自身を含む長さ1の区間、同じ頂点同士のLCAはその頂点である。自分自身も祖先に含めるが、深さを超えて何段も上の祖先を求める場合は「存在しない」と判定する。virtual treeは指定点0個なら空、1個ならその頂点だけとなる。頂点の値を経路に沿って読む場合は両端を含め、辺の値を読む場合はLCAの親辺を含めない。各表現の端点・順序と、前処理を含む費用を確認してから子単元へ進む。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

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

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。木を区間や祖先関係へ写し、配列上の算法へ接続する入口。

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

概念上の親: 木構造。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

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

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • LCAという概念で対象を一意分類するだけで、ancestor query・Euler区間化・HLD・virtual treeを実装利用しない数え上げ、および重心による再帰分解。

根拠