Day 071-Q4 — Level Ancestor Query（Binary Lifting + LCA統合）

問題

$N$ 頂点の根付き木（根 = 1）が与えられる。$Q$ 個のクエリに答えよ。

• LA v k: 頂点 $v$ の $k$ 個上の祖先の頂点番号（存在しない場合は -1）
• LCA u v: 頂点 $u$ と $v$ の最小共通祖先

入出力例

7 5
1 1 2 2 3 3
LA 5 2
LA 6 1
LCA 5 6
LA 4 3
LCA 4 7

1
2
2
-1
1

木の構造: 1→{2,3}, 2→{4,5}, 3→{6,7}。LA(5,2)=1（5の2個上は1）。LA(4,3)=-1（4の深さは2なので3個上は存在しない）。

概念図: Binary Lifting テーブル

ヒント（段階的開示）

LOG = 20
up = [[0] * (N + 1) for _ in range(LOG)]
up[0][root] = root  # 番哨

for k in range(1, LOG):
    for v in range(1, N + 1):
        up[k][v] = up[k-1][up[k-1][v]]

def la(v, k):
    if k < 0 or k > depth[v]: return -1
    for i in range(LOG):
        if (k >> i) & 1:
            v = up[i][v]
    return v

def lca(u, v):
    if depth[u] < depth[v]: u, v = v, u
    u = la(u, depth[u] - depth[v])
    if u == v: return u
    for k in range(LOG-1, -1, -1):
        if up[k][u] != up[k][v]:
            u = up[k][u]; v = up[k][v]
    return up[0][u]

模範解答 (Python)

コピーimport sys
from collections import deque
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]

    if N > 1:
        p_list = list(map(int, input().split()))
        for i, p in enumerate(p_list, start=2):
            parent[i] = p
            children[p].append(i)
    else:
        input()

    LOG = 20
    up = [[0] * (N + 1) for _ in range(LOG)]
    depth = [0] * (N + 1)

    root = 1
    up[0][root] = root  # 番哨
    bfs = deque([root])
    visited = [False] * (N + 1)
    visited[root] = True

    while bfs:
        v = bfs.popleft()
        for c in children[v]:
            if not visited[c]:
                visited[c] = True
                depth[c] = depth[v] + 1
                up[0][c] = v
                bfs.append(c)

    for k in range(1, LOG):
        for v in range(1, N + 1):
            up[k][v] = up[k-1][up[k-1][v]]

    def la(v, k):
        if k < 0 or k > depth[v]:
            return -1
        for i in range(LOG):
            if (k >> i) & 1:
                v = up[i][v]
        return v

    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        u = la(u, diff)
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u = up[k][u]
                v = up[k][v]
        return up[0][u]

    out = []
    for _ in range(Q):
        query = input().split()
        if query[0] == 'LA':
            v, k = int(query[1]), int(query[2])
            out.append(str(la(v, k)))
        else:
            u, v = int(query[1]), int(query[2])
            out.append(str(lca(u, v)))

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

solve()

Step-by-Step 解説

Step 1: Binary Lifting の仕組み

up[k][v] = 頂点 $v$ の $2^k$ 個上の祖先。再帰: up[k][v] = up[k-1][up[k-1][v]]

前処理 $O(N \log N)$、各クエリ $O(\log N)$。

Step 2: LA クエリ

$k$ を2進数で表し、ビットが立っている桁分ジャンプを繰り返す。例: $k = 5 = 101_2$ → $k=0$ のビット（1個上）→ $k=2$ のビット（4個上）の順にジャンプ。$k > \text{depth}(v)$ なら -1。

Step 3: LCA クエリ

1. 深い方を LA で同じ深さまで引き上げる
2. 同じ頂点なら LCA として返す
3. 大きい桁から試し、上が異なれば両方ジャンプ
4. 最後に一段上がれば LCA

Step 4: 番哨（Sentinel）

根の親を根自身に設定（up[0][root] = root）することで、「存在しない祖先」へのアクセスが根に収束し、境界処理が簡潔になる。ただし depth チェックは別途必要。

Step 5: 計算量分析

よくあるミス

次のステップ

• 発展問題: $O(N)$ 前処理 $O(1)$ クエリの LA アルゴリズム（Ladder Decomposition）
• LCA を使ったパスクエリ（HLD との統合）
• 動的木（頂点追加）上の LA クエリ（Link-Cut Tree）
• Level Ancestor と部分木クエリの組み合わせ問題

自己評価