View on GitHub

cp-library

Heavy-Light Decomposition

C++ 用ライブラリ一覧に戻る

nachia/tree/heavy-light-decomposition.hpp

主な機能

$n$ 頂点の静的な根付き無向木 $T$ がある。頂点には番号(0-based) が振られている。

$T$ の頂点を適切な順序に並べた列を $A=(A[0],A[1],A[2], \ldots ,A[n-1])$ とする。各要素は toVtx で得られる。

様々なメンバを持つ。特に、 $T$ に対して以下の計算を行う。前処理の計算量は $O(n)$ である。

struct HeavyLightDecomposition

コンストラクタ

nachia::HeavyLightDecomposition(
    const Graph& tree,
    int root = 0
);

nachia::HeavyLightDecomposition(
    const CsrArray<int>& E = CsrArray<int>::Construct(1, {}),
    int root = 0
);

nachia::Graph とは？

nachia::CsrArray とは？

$\text{root}$ を根として、 heavy-light decomposition を行う。

木は隣接リストで与えてもよい。その場合、根付き木の親から子へ向かう辺は含まれていなければいけないが、親へ向かう辺は含まなくてもよい。

toSeq

int toSeq(int vtx) const;

$A[i]=v$ を満たす $i$ を返す。

toVtx

int toVtx(int seqidx) const;

$A[i]$ を返す。

toSeq2In, toSeq2Out

int toSeq2In(int vtx) const;
int toSeq2Out(int vtx) const;

toSeq で得られる順序と同じ順序で DFS を行いながら、各頂点で次の $2$ 回タイミングを記録したとする。

これにより $2n$ 回タイミングが記録されるが、それに順に $0,1,\ldots ,2n-1$ の番号を振る。この関数では、このように付けられた番号を取得する。

depth

int depth(int p) const;

頂点 $p$ の深さ（つまり、根と頂点 $p$ との距離）を返す。

parentOf

int parentOf(int v) const;

頂点 $v$ の親の番号を返す。 $v$ が根の場合は $-1$ を返す。

heavyRootOf, heavyChildOf

int heavyRootOf(int v) const;  // (1)
int heavyChildOf(int v) const; // (2)

(1) : 頂点 $v$ と同じ heavy path に含まれている頂点のうち、最も根に近い頂点を返す。

(2) : 頂点 $v$ に heavy path でつながれた子の番号を返す。存在しない場合、 $-1$ を返す。

lca

int lca(int x, int y) const;

$\text{LCA}(x,y)$ を返す。

dist

int dist(int x, int y) const;

$\text{dist}(x,y)$ を返す。

path

vector<Range> path(int r, int c, bool include_root = true, bool reverse_path = false) const;

$r$ から $c$ へ向かう単純パスをいくつかの半開区間 $[l _ 0,r _ 0),[l _ 1,r _ 1),\cdots ,[l _ {k-1},r _ {k-1})$ で表し、一列に並べて返す。

パスに含まれる頂点の列を $(r=I _ 0,I _ 1,I _ 2, \cdots ,I _ {L-1}=c)$ 、と表したとき、 $2$ つの数列

は一致する。

include_root が false のとき、 $r$ から $c$ へ向かう単純パスは $r$ を除いたものとする。 reverse_path が true のとき、返す直前に次の手順を実行する。

  1. 返す配列を逆順にする。
  2. 各ペア $(l _ i,r _ i)$ を $(n-r _ i,n-l _ i)$ に変更する。

$c$ から $r$ へ向かうパスを扱うときは、数列 $A$ を逆順にとり、 reverse_path を真にしてこの関数を利用するとよい。

Range は以下で定義される。

struct Range{
    int l; int r;
    int size() const { return r-l; }
    bool includes(int x) const { return l <= x && x < r; }
};

subtree

Range subtree(int r) const;

頂点 $r$ の部分木を半開区間 $[l _ 0,r _ 0)$ で表したものを返す。

頂点 $r$ の部分木に含まれる頂点をある DFS の行きがけ順に並べた列を $(r=I _ 0,I _ 1, \cdots ,I _ {L-1})$ としたとき、 $2$ つの数列

は一致する。

median

int median(int x, int y, int z) const;

頂点・辺の構造はそのままで根を頂点 $x$ に変更したときの $\text{LCA}(y,z)$ を返す。

$\text{median}(x,y,z)$ の性質として、 $x,y,z$ の順番をどのように入れ替えても結果は変わらない。

la

int la(int from, int to, int d) const;

$0 \leq d \leq \text{dist(from,to)}$ のとき、 $\text{from}$ から $\text{to}$ へ向かう単純パスにおいて、 $\text{from}$ から距離 $d$ の位置にある頂点を返す。それ以外のとき、 $-1$ を返す。

これは、 $\text{from}$ を根としたときの Level Ancestor と同じことである。

children

ChildrenIterRange children(int v) const;

次のように呼び出すことで、 $v$ の子が列挙される。 $1$ ステップごとに $O(1)$ 時間で返す。

for(int w : hld.children(v)){
    // do with w
}

参考

TOP PAGE