最小共通祖先 (Tarjan のオフラインアルゴリズム)
(Graph/Tree/offline_lca.py)

• View this file on GitHub
• Last update: 2021-06-20 02:02:14+09:00

概要

最小共通先祖クエリにオフラインで答えるアルゴリズム。

使い方

offline_lca(tree: Sequence[Iterable[int]], queries: Sequence[Tuple[int, int]], root: int) -> List[int]
根が root である木 tree に対して LCA を求める。計算量 $O(V + Q)$

$i$ 番目のクエリ queries[i] の意味は次の通りである。

u v

頂点 $u$ と頂点 $v$ の LCA は何か？

参考

• Lowest Common Ancestor - Tarjan’s off-line algorithm - Competitive Programming Algorithms

Depends on

• Union Find (DataStructure/UnionFind/UnionFind.py)

Verified with

• TestCase/LibraryChecker/lca.offline.test.py

Code

from DataStructure.UnionFind.UnionFind import UnionFind


def offline_lca(tree, queries, root):
    n = len(tree)
    q = len(queries)
    uf = UnionFind(n)
    par = [-1] * n
    anc = [-1] * n
    ans = [-1] * q
    qs = [[] for i in range(n)]
    for i, (u, v) in enumerate(queries):
        qs[u].append((v << 24) + i)
        qs[v].append((u << 24) + i)

    stack = [root]
    while stack:
        v = stack.pop()
        if v < 0:
            v = ~v
            for tmp in qs[v]:
                nxt_v = tmp >> 24
                i = tmp - (nxt_v << 24)
                ans[i] = anc[uf.root(nxt_v)]
            uf.merge(par[v], v)
            anc[uf.root(par[v])] = par[v]
            continue
        stack.append(~v)
        for nxt_v in tree[v]:
            if par[v] == nxt_v:
                continue
            par[nxt_v] = v
            stack.append(nxt_v)
    return ans

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