HL分解 (Heavy-Light Decomposition)
(Graph/Tree/HLDecomposition.py)

• View this file on GitHub
• Last update: 2021-01-16 03:42:28+09:00

概要

木に対して HL 分解 (Heavy-Light Decomposition) を行い、列としてのクエリ処理を可能にするアルゴリズム。

使い方

HLDecomposition(tree: Sequence[Iterable[int]])
隣接リストで表現される木 Tree に対して HL 分解を行う。森にも対応している。根頂点を指定できないことに注意。木の場合、根は頂点 0 となる。 計算量 $O(V)$

• __getitem__(v: int) -> int
  木の頂点 v に対応する列のインデックスを返す。計算量 $O(1)$

• lca(u: int, v: int) -> int
u と v の最小共通祖先を返す。u と v が非連結の場合は -1 を返す。計算量 $O(\log V)$

• distance(u: int, v: int) -> int
u - v パスの距離を返す。u と v が非連結の場合は -1 を返す。計算量 $O(\log V)$

• range_vertex_path(u: int, v: int) -> Iterator[Tuple[int, int]]
u - v パス上の頂点に対応する列の区間集合をイテレータとして返す。区間は半開区間である。u と v が非連結の場合は未定義。イテレートにかかる計算量 $O(\log V)$

• range_edge_path(u: int, v: int) -> Iterator[Tuple[int, int]]
u - v パス上の辺に対応する列の区間集合をイテレータとして返す。区間は半開区間である。u と v が非連結の場合は未定義。イテレートにかかる計算量 $O(\log V)$

• range_subtree(u: int) -> Tuple[int, int]
u を根とした部分木に対応する列の区間を返す。区間は半開区間である。計算量 $O(1)$

参考

• 【図解】木のパスに関するクエリは HL 分解！ その仕組みと実装を図で理解する｜Heavy-Light Decomposition - Qiita
• Easiest HLD with subtree queries - Codeforces

Verified with

• TestCase/AOJ/2667.test.py
• TestCase/AOJ/GRL_5_D.test.py
• TestCase/AOJ/GRL_5_E.test.py
• TestCase/LibraryChecker/lca.HLDecomposition.test.py
• TestCase/LibraryChecker/vertex_add_path_sum.test.py
• TestCase/LibraryChecker/vertex_add_subtree_sum.test.py
• TestCase/yukicoder/yuki0922.HLDecomposition.test.py

Code

class HLDecomposition:
    def __init__(self, tree):
        self.tree = tree
        self.n = len(tree)
        self.par = [-1] * self.n
        self.size = [1] * self.n
        self.depth = [0] * self.n
        self.preorder = [0] * self.n
        self.head = [i for i in range(self.n)]
        self.k = 0

        for v in range(self.n):
            if self.par[v] == -1:
                self._dfs_pre(v)
                self._dfs_hld(v)

    def __getitem__(self, v):
        return self.preorder[v]

    def _dfs_pre(self, v):
        tree = self.tree
        stack = [v]
        order = [v]
        while stack:
            v = stack.pop()
            for chi_v in tree[v]:
                if chi_v == self.par[v]:
                    continue
                self.par[chi_v] = v
                self.depth[chi_v] = self.depth[v] + 1
                stack.append(chi_v)
                order.append(chi_v)

        for v in reversed(order):
            tree_v = tree[v]
            if len(tree_v) and tree_v[0] == self.par[v]:
                tree_v[0], tree_v[-1] = tree_v[-1], tree_v[0]
            for idx, chi_v in enumerate(tree_v):
                if chi_v == self.par[v]:
                    continue
                self.size[v] += self.size[chi_v]
                if self.size[chi_v] > self.size[tree_v[0]]:
                    tree_v[idx], tree_v[0] = tree_v[0], tree_v[idx]

    def _dfs_hld(self, v):
        stack = [v]
        while stack:
            v = stack.pop()
            self.preorder[v] = self.k
            self.k += 1
            if len(self.tree[v]) == 0:
                continue
            top = self.tree[v][0]
            for chi_v in reversed(self.tree[v]):
                if chi_v == self.par[v]:
                    continue
                if chi_v == top:
                    self.head[chi_v] = self.head[v]
                else:
                    self.head[chi_v] = chi_v
                stack.append(chi_v)

    def lca(self, u, v):
        while u != -1 and v != -1:
            if self.preorder[u] > self.preorder[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                return u
            v = self.par[self.head[v]]
        return -1

    def distance(self, u, v):
        lca_uv = self.lca(u, v)
        if lca_uv == -1:
            return -1
        else:
            return self.depth[u] + self.depth[v] - 2 * self.depth[lca_uv]

    def range_vertex_path(self, u, v):
        while True:
            if self.preorder[u] > self.preorder[v]:
                u, v = v, u
            l = max(self.preorder[self.head[v]], self.preorder[u])
            r = self.preorder[v]
            yield l, r + 1
            if self.head[u] != self.head[v]:
                v = self.par[self.head[v]]
            else:
                return

    def range_edge_path(self, u, v):
        while True:
            if self.preorder[u] > self.preorder[v]:
                u, v = v, u
            if self.head[u] != self.head[v]:
                yield self.preorder[self.head[v]], self.preorder[v] + 1
                v = self.par[self.head[v]]
            else:
                if u != v:
                    yield self.preorder[u] + 1, self.preorder[v] + 1
                break

    def range_subtree(self, u):
        return self.preorder[u], self.preorder[u] + self.size[u]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page