Auxiliary Tree, Virtual Tree

概要

\(N\)個の頂点を含む根付き木\(T\) より、とある頂点集合 \(X = {v_1, v_2, ..., v_K}\) と それらのLCAを含むような木を構築する。

頂点集合\(X\)に対し、以下の手順によって構築できる。

  1. 頂点集合\(X\)を、グラフ\(G\)をDFSした時のpre-orderの順序で並べる

    • このリストを \(A = v_{i_1}, v_{i_2}, ..., v_{i_K}\) とする

  2. \(1 \le j < K\) に対し、 \(w = lca(v_{i_j}, v_{i_{j+1}})\) を求める

  3. 頂点集合\(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

Verified

  • Codeforces: "613D: Kingdom and its Cities": source (PyPy3, 920ms)