概要

根付き木\(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の子頂点 (親頂点は含まない)

# 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