最小共通祖先 (ダブリング)
(Graph/Tree/DoublingLCA.py)

• View this file on GitHub
• Last update: 2022-09-04 19:01:08+09:00

概要

木に対して $O(V \log V)$ で構築し、$O(\log V)$ で最小共通先祖クエリに答えるアルゴリズム。森にも対応している。

使い方

DoublingLCA(tree: Sequence[Iterable[int]], root: Optional[int] = None)
隣接リストで表現される木 tree に対してダブリングを行う。根頂点 root を指定しない場合は、頂点 0 が根となる。計算量 $O(V\log V)$

• 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)$

• jump(u: int, v: int, k: int) -> int
u - v パス上の頂点で u からの距離が k の頂点を返す。そのような頂点が存在しない場合は -1を返す。計算量 $O(\log V)$

Verified with

• TestCase/LibraryChecker/jump_on_tree.Doubling.test.py
• TestCase/LibraryChecker/lca.Doubling.test.py
• TestCase/yukicoder/yuki0922.test.py

Code

class DoublingLCA:
    def __init__(self, tree, root=None):
        self.n = len(tree)
        self.depth = [0] * self.n
        self.log_size = (self.n).bit_length()
        self.parent = [[-1] * self.n for i in range(self.log_size)]

        if root is None:
            for v in range(self.n):
                if self.parent[0][v] == -1:
                    self._dfs(v, tree)
        else:
            self._dfs(root, tree)

        for k in range(self.log_size - 1):
            for v in range(self.n):
                if self.parent[k][v] == -1:
                    self.parent[k + 1][v] = -1
                else:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]

    def _dfs(self, rt, tree):
        stack = [(rt, -1)]
        while stack:
            v, par = stack.pop()
            for chi_v in tree[v]:
                if chi_v == par:
                    continue
                self.parent[0][chi_v] = v
                self.depth[chi_v] = self.depth[v] + 1
                stack.append((chi_v, v))

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        for k in range(self.log_size):
            if ((self.depth[v] - self.depth[u]) >> k) & 1:
                v = self.parent[k][v]
        if u == v:
            return u
        for k in reversed(range(self.log_size)):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    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 jump(self, u, v, k):
        if k == 0:
            return u
        lca_uv = self.lca(u, v)
        du = self.depth[u] - self.depth[lca_uv]
        dv = self.depth[v] - self.depth[lca_uv]
        if du + dv < k:
            return -1
        if k <= du:
            d = k
        else:
            u = v
            d = du + dv - k
        i = 0
        while d > 0:
            if d & 1:
                u = self.parent[i][u]
            d >>= 1
            i += 1
        return 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