概要
根付き木 \(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)