Day 136-Q2 | Farach-Colton and Bender型 O(1) LCA

問題

$N$ 頂点の根付き木（根は頂点 $1$）が与えられる。$Q$ 個のクエリ u v それぞれについて、頂点 $u, v$ の最小共通祖先（LCA）を答えよ。

前処理 $O(N)$ 前後（本問では実装簡略化のため許容範囲を広めに取る）、各クエリ $O(1)$ で応答する「±1 RMQ に基づく LCA」（Farach-Colton and Bender の手法）を実装せよ。

入力形式

N Q
a_1 b_1
...
a_{N-1} b_{N-1}
u_1 v_1
...
u_Q v_Q

制約

$1 \le N, Q \le 2\times10^5$

$1 \le a_i,b_i,u_j,v_j \le N$

与えられるグラフは木

入出力例

入力例1

出力例1

概念図

ヒント（段階的開示）

ヒント1（方向性）

LCA(u,v) は「オイラーツアーで頂点を訪れる順に並べ、深さ配列を作り、$u$ の最初の出現位置から $v$ の最初の出現位置までの区間で深さが最小になる位置の頂点」として求まる。この配列は隣接差が必ず $\pm1$ という特殊な性質を持つ。

ヒント2（アプローチ）

配列を長さ $b\approx\frac12\log_2 M$ のブロックに分割する。ブロック同士の最小値比較は Sparse Table で $O(1)$。ブロック内部の最小値は「$\pm1$の増減パターン」だけで決まり、パターン数は $2^{b-1}\approx\sqrt M$ 通りしかない。同じパターンのブロックは局所テーブルを共有できる。

ヒント3（誘導）

def get_table(length, pattern):
    key = (length, pattern)
    if key in cache:
        return cache[key]
    rel = [0] * length
    for j in range(1, length):
        bit = (pattern >> (j - 1)) & 1
        rel[j] = rel[j - 1] + (1 if bit else -1)
    table = [[0] * length for _ in range(length)]
    for l in range(length):
        table[l][l] = l
        for r in range(l + 1, length):
            prev = table[l][r - 1]
            table[l][r] = prev if rel[prev] <= rel[r] else r
    cache[key] = table
    return table

クエリ [l,r] は「左端の部分ブロック・右端の部分ブロック・その間の完全なブロック群」の3候補を比較して最小を選ぶ。

模範解答 (Python)

import sys


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1

    adj = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a = int(data[idx]); idx += 1
        b = int(data[idx]); idx += 1
        adj[a].append(b)
        adj[b].append(a)

    depth = [0] * (N + 1)
    first = [-1] * (N + 1)
    M = 2 * N - 1
    euler = [0] * M
    depth_arr = [0] * M
    visited = [False] * (N + 1)

    pos = 0
    euler[pos] = 1
    depth_arr[pos] = 0
    first[1] = pos
    pos += 1
    visited[1] = True

    stack = [1]
    iters = [iter(adj[1])]
    while stack:
        u = stack[-1]
        moved = False
        for v in iters[-1]:
            if not visited[v]:
                visited[v] = True
                depth[v] = depth[u] + 1
                first[v] = pos
                euler[pos] = v
                depth_arr[pos] = depth[v]
                pos += 1
                stack.append(v)
                iters.append(iter(adj[v]))
                moved = True
                break
        if not moved:
            stack.pop()
            iters.pop()
            if stack:
                p = stack[-1]
                euler[pos] = p
                depth_arr[pos] = depth[p]
                pos += 1

    b = max(1, M.bit_length() // 2)
    nb = (M + b - 1) // b
    block_start = [i * b for i in range(nb)]
    block_len = [min(b, M - block_start[i]) for i in range(nb)]

    cache = {}

    def get_table(length, pattern):
        key = (length, pattern)
        if key in cache:
            return cache[key]
        rel = [0] * length
        for j in range(1, length):
            bit = (pattern >> (j - 1)) & 1
            rel[j] = rel[j - 1] + (1 if bit else -1)
        table = [[0] * length for _ in range(length)]
        for l in range(length):
            table[l][l] = l
            for r in range(l + 1, length):
                prev = table[l][r - 1]
                table[l][r] = prev if rel[prev] <= rel[r] else r
        cache[key] = table
        return table

    block_table = [None] * nb
    block_min_idx = [0] * nb
    for i in range(nb):
        s = block_start[i]
        length = block_len[i]
        pat = 0
        for j in range(1, length):
            if depth_arr[s + j] > depth_arr[s + j - 1]:
                pat |= (1 << (j - 1))
        tbl = get_table(length, pat)
        block_table[i] = tbl
        block_min_idx[i] = tbl[0][length - 1]

    def block_min_global(i):
        return block_start[i] + block_min_idx[i]

    LOG = nb.bit_length() + 1
    sparse = [[0] * nb for _ in range(LOG)]
    for i in range(nb):
        sparse[0][i] = block_min_global(i)
    j = 1
    while (1 << j) <= nb:
        half = 1 << (j - 1)
        for i in range(nb - (1 << j) + 1):
            ai = sparse[j - 1][i]
            bi = sparse[j - 1][i + half]
            sparse[j][i] = ai if depth_arr[ai] <= depth_arr[bi] else bi
        j += 1

    def range_min_blocks(bl, br):
        length = br - bl + 1
        k = length.bit_length() - 1
        ai = sparse[k][bl]
        bi = sparse[k][br - (1 << k) + 1]
        return ai if depth_arr[ai] <= depth_arr[bi] else bi

    def query_min_idx(l, r):
        bl, ll = divmod(l, b)
        br, rr = divmod(r, b)
        if bl == br:
            return block_start[bl] + block_table[bl][ll][rr]
        tbl_l = block_table[bl]
        cand1 = block_start[bl] + tbl_l[ll][block_len[bl] - 1]
        tbl_r = block_table[br]
        cand2 = block_start[br] + tbl_r[0][rr]
        best = cand1 if depth_arr[cand1] <= depth_arr[cand2] else cand2
        if br - bl > 1:
            cand3 = range_min_blocks(bl + 1, br - 1)
            if depth_arr[cand3] < depth_arr[best]:
                best = cand3
        return best

    def lca(u, v):
        l, r = first[u], first[v]
        if l > r:
            l, r = r, l
        return euler[query_min_idx(l, r)]

    out = []
    for _ in range(Q):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        out.append(str(lca(u, v)))

    print("\n".join(out))


main()

Step-by-Step 解説

1オイラーツアーでLCAを区間最小値に帰着
木をDFSで辿り、頂点に入るたび／親に戻るたびに頂点番号を記録すると長さ$2N-1$の列ができる。$u,v$の最初の出現区間の深さ最小位置がLCA。

2深さ配列の±1性質
1歩ごとに深さが+1か-1しか変化しない制約付きRMQ（±1 RMQ）は、一般のRMQより強い前処理でO(1)クエリを達成できる。

3ブロック分割とパターン共有
ブロック内の増減パターンは$2^{b-1}$通りしかなく、同じパターンのブロックは同じ局所minテーブルを再利用できる。

4ブロック間はスパーステーブル
完全に含まれる中間ブロック群の最小値比較は「各ブロックの最小値」を1要素とするSparse TableでO(1)。

53候補の統合
「左端ブロックの右側部分」「右端ブロックの左側部分」「中間の完全ブロック群」の3候補を比較し最小値の位置を決定する。

よくあるミス

ミス	原因	正しい書き方
オイラーツアーを再帰実装して深さ制限に触れる	Nが大きいと再帰が深くなる	スタックを使った反復DFSで構築する
パターンテーブルと実データを混同	パターンは相対順序のみ表す	局所インデックスのみ取り出し、比較は元のdepth_arrで行う
部分ブロックの範囲指定を誤る	左端は後半、右端は前半を切り出す点を取り違える	左端`[ll, len-1]`、右端`[0, rr]`を正しく指定
ブロック数1のとき範囲外参照	中間ブロックのクエリが呼ばれない前提が崩れる	`br-bl>1`の場合のみ`range_min_blocks`を呼ぶ
first[u]とfirst[v]の大小を確認しない	区間が逆転し範囲外アクセスになる	`l>r`ならswapしてから区間を確定

次のステップ

発展: 本実装はパターンキャッシュで前処理$O(\sqrt M\log^2 M)$程度に収まるが、真の手法では$O(N)$ちょうどまで詰める工夫がある。追加最適化を調べよ。
発展2: LCAが求まれば距離クエリdist(u,v)=depth[u]+depth[v]-2*depth[lca(u,v)]も追加実装せよ。

自己評価

完全理解おおむね理解要復習

Day 136-Q2 — Farach-Colton and Bender型 O(1) LCA（±1 RMQ）

問題