Day 107-Q4 | Ladder Decomposition（真のO(1) Level Ancestor Query）

問題

$N$頂点の根付き木が与えられる（根は頂点$1$）。$Q$個のクエリv dに対して、「頂点$v$から$d$回親を辿った先の頂点」（$d$世代上の祖先）を出力せよ。存在しなければ（$d$が$v$の深さを超えるなら）-1を出力せよ。

二分累乗（ダブリング）だけでも$O(\log N)$で答えられるが、Ladder Decomposition（長path分解 + ジャンプポインタの併用）を使うと前処理$O(N\log N)$のまま、クエリを真の$O(1)$で処理できる。

入力形式

N
p_2 p_3 ... p_N
Q
v_1 d_1
...
v_Q d_Q

制約

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

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

$1 \le p_i < i$

$0 \le d_i \le N$

入出力例

入力例1

8
1 1 3 4 3 2 1
5
7 1
7 2
7 3
7 5
5 10

出力例1

2
1
-1
-1
-1

木構造: 1の子は2,3,8。2の子は7。3の子は4,6。4の子は5。頂点7の深さは2（1→2→7）なので、1世代上は2、2世代上は1、3世代以上は無く-1。頂点5の深さは3なのでd=10は-1。

概念図: 長path分解とladder（はしご）

ヒント（段階的開示）

ヒント1: 方向性

各頂点に親へのポインタを$2^0,2^1,2^2,\dots$分の距離であらかじめ計算しておく二分累乗（binary lifting）を使えば、$d$を2進数分解して$O(\log d)$回のジャンプで祖先に到達できる。しかし「真の$O(1)$」を達成するには、二分累乗を最後の仕上げにしか使わず、残りは配列の直接インデックスアクセスだけで済ませる工夫が必要になる。

ヒント2: アプローチ

木を「長path分解」する：各頂点で部分木の高さが最大になる子を「重い子」とし、そこだけ親と同じpathが続くとみなす。これにより木は互いに素な縦に長いパスの集まりに分割される。さらに各pathについて、「path自体（長さh）」に加えて「pathの先頭からさらに上へh個分の祖先」を連結したladderを作る。ladderの長さはpathの長さの最大2倍になり、path上のどの頂点から見てもh個以内上までは配列の直接参照$O(1)$でアクセスできる。クエリ(v,d)は、まず二分累乗で$2^j$（$j=\lfloor\log_2 d\rfloor$）だけジャンプして頂点uに移動する。このuが属するpathの長さは必ず$2^j$以上あることが保証されるため、残りの距離はuのpathのladder配列に対する直接インデックスで$O(1)$取得できる。

ヒント3: 誘導（コード骨格）

def query(v, d):
    if d == 0: return v
    if d > depth[v]: return -1
    j = d.bit_length() - 1
    u = up[j][v]            # 二分累乗でまず 2^j 分ジャンプ
    d_rem = d - (1 << j)
    t = path_top[u]
    pos = idx_in_path[u]
    if d_rem <= pos:
        return path_nodes[t][pos - d_rem]     # path内なので直接インデックス
    rem2 = d_rem - pos
    return up_ext[t][rem2 - 1]                 # path先頭より上、ladderで直接インデックス

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    parent = [-1] * N
    for v in range(1, N):
        parent[v] = int(data[idx]) - 1; idx += 1
    root = 0

    children = [[] for _ in range(N)]
    for v in range(1, N):
        children[parent[v]].append(v)

    depth = [0] * N
    bfs_order = [root]
    i = 0
    while i < len(bfs_order):
        u = bfs_order[i]; i += 1
        for c in children[u]:
            depth[c] = depth[u] + 1
            bfs_order.append(c)

    h = [0] * N
    for u in reversed(bfs_order):
        h[u] = 1 + max((h[c] for c in children[u]), default=-1)

    heavy = [-1] * N
    for u in range(N):
        best, bh = -1, -1
        for c in children[u]:
            if h[c] > bh:
                bh, best = h[c], c
        heavy[u] = best

    path_top = [0] * N
    path_top[root] = root
    for u in bfs_order:
        if u == root:
            continue
        p = parent[u]
        path_top[u] = path_top[p] if heavy[p] == u else u
    idx_in_path = [depth[u] - depth[path_top[u]] for u in range(N)]

    path_nodes = {}
    for u in bfs_order:
        if path_top[u] == u:
            nodes = [u]
            cur = u
            while heavy[cur] != -1:
                cur = heavy[cur]
                nodes.append(cur)
            path_nodes[u] = nodes

    up_ext = {}
    for t, nodes in path_nodes.items():
        L = len(nodes)
        ext = []
        cur = t
        for _ in range(L):
            if cur == root:
                break
            cur = parent[cur]
            ext.append(cur)
        up_ext[t] = ext

    LOG = max(1, N.bit_length() + 1)
    up = [[-1] * N for _ in range(LOG)]
    up[0] = parent[:]
    for j in range(1, LOG):
        prevj = up[j - 1]
        for v in range(N):
            mid = prevj[v]
            up[j][v] = -1 if mid == -1 else prevj[mid]

    def query(v, d):
        if d == 0:
            return v
        if d > depth[v]:
            return -1
        j = d.bit_length() - 1
        u = up[j][v]
        d_rem = d - (1 << j)
        t = path_top[u]
        pos = idx_in_path[u]
        if d_rem <= pos:
            return path_nodes[t][pos - d_rem]
        rem2 = d_rem - pos
        ext = up_ext[t]
        return ext[rem2 - 1] if rem2 - 1 < len(ext) else -1

    Q = int(data[idx]); idx += 1
    out = []
    for _ in range(Q):
        v = int(data[idx]) - 1; idx += 1
        d = int(data[idx]); idx += 1
        r = query(v, d)
        out.append(str(r + 1) if r != -1 else "-1")
    print('\n'.join(out))


solve()

計算量: 前処理 $O(N\log N)$、クエリ1回あたり真の $O(1)$。ランダム300ケース×50クエリで祖先チェーン愚直辿りと一致することを確認済み。

Step-by-Step 解説

1長path分解で木を縦に長いパスの集まりに分割
各頂点の部分木の高さh[v]をボトムアップで計算し、最大のhを持つ子をheavyとする。ある頂点が属するpathの長さはその頂点を根とする部分木の高さhに等しい。

2ladder（path + 同じ長さの上方拡張）を作る
各pathの先頭tについて、path自体（長さh[t]）に加えて、さらにh[t]個分の祖先をup_ext[t]として保持。ladder全体の長さはpathの長さの高々2倍で、全pathのladder合計サイズはO(N)。

3クエリは「二分累乗で1回ジャンプ→ladderで直接インデックス」
j=⌊log2 d⌋として2^j分だけ二分累乗テーブルでジャンプする。ジャンプ先uが属するpathの長さは必ずh[u]≥2^jが保証され、残りの距離はpath_nodesまたはup_extの範囲内に収まり配列参照だけでO(1)。

4二分累乗テーブル自体はO(N log N)で普通に構築
クエリごとに使うのはこのテーブルの参照1回だけなので、クエリ全体の計算量はO(1)に保たれる。

よくあるミス

ミス	原因	正しい書き方
j=0（d=1）のときにジャンプを省略してしまう	「j>0のときだけジャンプする」という誤った条件分岐	j=0でもup[0][v]（親そのもの）を使って必ず1回ジャンプする
up_ext[t]の長さがpathの長さh[t]を超えると誤解する	根に近いpathでは祖先の数がh[t]に届かないことがある	up_ext[t]の実際の長さで範囲チェック（rem2-1 < len(ext)）を必ず行う
h[v]の定義を「深さ」と混同する	h[v]は「vを根とする部分木の高さ」でありグローバルなdepth[v]とは別物	heavy child判定には必ずhを使い、depthと混同しない
クエリのdが深さを超える場合の判定漏れ	up[j][v]=-1を辿ると誤ったインデックスアクセスになる	クエリ処理の最初に`if d > depth[v]: return -1`を必ず入れる

次のステップ

発展: 頂点の追加・削除がある動的な木でLevel Ancestorを維持する（Euler Tour TreeやTop Treeとの組み合わせが必要）
発展: 真に$O(N)$前処理（$O(N\log N)$ではなく）を達成する（Sparse Table型の±1 RMQをEuler Tourに適用する手法）
次回予告: 凸コストMin-Cost-Flow（辺の凸コストを単位容量辺に分解して最適化する）

自己評価

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

Day 107-Q4 — Ladder Decomposition（真のO(1) Level Ancestor Query）

問題