Offline Level Ancestor Θ(N+Q)

概要

シンプルなアルゴリズムですが、Level Ancestor Problem 自体の知名度が低そうなので宣伝を兼ねて紹介します。

Level Ancestor

Level Ancestor とは、根付き木について定義される概念です。
$LA ( v , d ) := v$ の祖先であって、深さが $d$ であるもの ( $v$ の深さ $\geq d$ )

f:id:noshi91:20190922114110p:plain

$v$ の深さが分かれば「 $v$ から根の方向に $k$ 回親を辿った頂点は何か」というクエリを Level Ancestor を求める問題に帰着できます。逆もまた帰着可能なので、多くの状況でこれらは同一の問題とみなすことが出来ます。

アルゴリズム

$N$ 頂点の根付き木と $Q$ 個のクエリ $( v , d )$ が与えられたとき、全てのクエリの結果を $\Theta ( N + Q )$ で得るアルゴリズムを示します。
木を DFS で走査しながら、「(根～現在居る頂点)のパス」を配列で管理します。これは単に頂点に入ったとき push_back し、出るとき pop_back すればよいです。 $LA ( v , d )$ は $v$ に居る時の配列の $d$ 番目の要素になります。

実装例

NoshiMochiLibrary/offline_level_ancestor.hpp at offline_level_ancestor · NiMiLib/NoshiMochiLibrary · GitHub

応用

$\lbrack 0 , N ) \rightarrow \lbrack 0 , N )$ の写像の累乗は $\Theta ( N )$ で計算できる。
このような写像は functional graph と呼ばれる構造を成し、これはサイクルと内向木に分解可能である。 $x$ 乗とは各頂点 $v$ について $x$ 回辺を辿った頂点を計算することであるから、 $v$ の深さを $d$ とすると $d \le x$ ならばサイクルを $x - d$ だけ回ればよく、 $d \geq x$ なら $LA ( v , d - x )$ が答えとなる。これは前述した offline LA で $\Theta ( N )$ で計算可能。