Auxiliary Tree, Virtual Tree
概要
\(N\) 個の頂点を含む根付き木 \(T\) より、とある頂点集合 \(X = {v_1, v_2, ..., v_K}\) と それらのLCAを含むような木を構築する。
頂点集合 \(X\) に対し、以下の手順によって構築できる。
-
頂点集合 \(X\) を、グラフ \(G\) をDFSした時のpre-orderの順序で並べる
-
このリストを \(A = v_{i_1}, v_{i_2}, ..., v_{i_K}\) とする
-
-
\(1 \le j < K\) に対し、 \(w = lca(v_{i_j}, v_{i_{j+1}})\) を求める
-
頂点集合 \(X\) と(2)のlcaの頂点から、Auxiliary Treeを構築する
ここでは、具体的に以下で構築する
-
(2)において、各 \(1 \le j < K\) に対し求めたlca \(w\) をリスト \(A\) に追加する
-
リスト \(A\) に含まれる頂点をもう一度pre-orderの順序で並べる
-
リスト \(A\) に含まれる頂点 \(v_i\) を走査しながら、stackを用いてリスト \(A\) に含まれる直近の祖先 \(v_j\) を求める
頂点集合 \(X\) のサイズを \(K\) とすると、このAuxiliary Treeの頂点数は高々 \(2K-1\) になる。
計算量
Euler Tour TechniqueとSparse Tableを用いた場合
-
前計算: \(O(N \log N)\)
-
Auxiliary Treeの構築: \(O(K \log K)\)
Euler Tour TechniqueとSegment Treeを用いた場合
-
前計算: \(O(N)\)
-
Auxiliary Treeの構築: \(O(K (\log K + \log N))\)
実装 (ETT + Sparse Table)
# Auxiliary Tree を保持する
G0 = None
S = None
FS = LS = depth = None
lg = None
st = None
# 前計算 O(N log N)
def construct(N, G):
global S, FS, LS, depth, G0, lg, st
G0 = [None] * N
S = []
FS = [0]*N; LS = [0]*N
depth = [0]*N
# Euler tour technique
def dfs(v, p, d):
depth[v] = d
FS[v] = len(S)
S.append(v)
for w in G[v]:
if w == p:
continue
dfs(w, v, d+1)
S.append(v)
LS[v] = len(S)
S.append(v)
dfs(0, -1, 0)
# Sparse Table
L = len(S)
lg = [0]*(L+1)
for i in range(2, L+1):
lg[i] = lg[i >> 1] + 1
st = [[L]*(L - (1 << i) + 1) for i in range(lg[L]+1)]
st[0][:] = S
b = 1
for i in range(lg[L]):
st0 = st[i]
st1 = st[i+1]
for j in range(L - (b<<1) + 1):
st1[j] = (st0[j] if depth[st0[j]] <= depth[st0[j+b]] else st0[j+b])
b <<= 1
# 頂点リストvsを含むAuxiliary Treeを構築 O(K log K)
def auxiliary_tree(k, vs):
vs.sort(key=FS.__getitem__)
for i in range(k-1):
x = FS[vs[i]]; y = FS[vs[i+1]]
l = lg[y - x + 1]
w = st[l][x] if depth[st[l][x]] <= depth[st[l][y - (1 << l) + 1]] else st[l][y - (1 << l) + 1]
vs.append(w)
vs.sort(key=FS.__getitem__)
stk = []
prv = -1
for v in vs:
if v == prv:
continue
while stk and LS[stk[-1]] < FS[v]:
stk.pop()
if stk:
G0[stk[-1]].append(v)
G0[v] = []
stk.append(v)
prv = v