概要

根付き木 \(T\) のある頂点 \(u, v\) について、共通の祖先であり、根頂点から最も遠い位置にあるLCAの頂点を求める。

セグメント木を使ったアルゴリズムでは、Euler tour techniqueを用いてLCAを計算する。

具体的計算

蟻本ベース[1]の説明

DFSでグラフ \(T\) を根から探索した際の頂点の訪問順を並べた列 \(S = (v_0, v_1, ..., v_{M-1})\) を求め、これをセグメント木に載せる。 また、頂点 \(v\) の根からの深さ \(depth_v\) と、頂点 \(v\) がこの列に最初に出現した位置 \(F_v\) も計算しておく。

セグメント木の \(i\) 番目の要素には、 \((depth_{v_i} , v_i)\) を持たせておく。

頂点 \(u, v\) のLCAの計算では、 \(\min(F_u, F_v) \le i \le \max(F_u, F_v)\) となる \(i\) の中で、 \(depth_{v_i}\) が最小となるような \(i\) を求め、 \(v_i\) をLCAとする。

前計算は計算量 \(O(N)\) となり、各クエリごとに \(O(\log N)\) となる。

計算量

  • 前計算: \(O(N)\)

  • クエリ処理: \(O(\log N)\)

実装

# N: 頂点数
# G[v]: 頂点vの子頂点 (親頂点は含まない)
N = ...
G = [[...] for i in range(N)]

# Euler Tour の構築
S = []
F = [0]*N
depth = [0]*N
def dfs(v, d):
    F[v] = len(S)
    depth[v] = d
    S.append(v)
    for w in G[v]:
        dfs(w, d+1)
        S.append(v)
dfs(0, 0)

# 存在しない範囲は深さが他よりも大きくなるようにする
INF = (N, None)

# LCAを計算するクエリの前計算
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])

# LCAの計算 (generatorで最小値を求める)
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1

# LCAの計算 (外から呼び出す関数)
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

Verified

  • AOJ: "GRL_5_C: Tree - Lowest Common Ancestor": source (Python3, 1.70sec)


戻る


1. プログラミングコンテストチャレンジブック [第2版] p.295