概要

根付き木において、2つの頂点の最小共通祖先 (LCA: Lowest Common Ancestor) を求める問題です。ダブリング（Binary Lifting）を用いて各クエリに高速に答えます。

考察

問題の言い換え

「社員 \(X\) と社員 \(Y\) の両方の上司であり、深さが最も大きい社員」とは、根付き木における \(X\) と \(Y\) の 最小共通祖先（LCA） そのものです。

素朴なアプローチとその問題点

最も単純な方法は、\(X\) と \(Y\) それぞれから親を1つずつたどって合流する地点を探すことです。

• \(X\) と \(Y\) の深さを揃える → 深い方を1つずつ上に移動
• 深さが同じになったら、両方を1つずつ上に移動して一致するまで繰り返す

この場合、1回のクエリに最大 \(O(N)\) かかるため、全体で \(O(NQ)\) となり、\(N = 3 \times 10^5\), \(Q = 5 \times 10^4\) では最大 \(1.5 \times 10^{10}\) 回の操作となりTLEします。

解決策：ダブリング（Binary Lifting）

「1つずつ上にたどる」代わりに、「\(2^k\) 個上の祖先」を事前に計算しておけば、\(O(\log N)\) で任意の距離を一気にジャンプできます。これにより各クエリを \(O(\log N)\) で処理できます。

アルゴリズム

1. 前処理：ダブリングテーブルの構築

\(up[k][v]\) = 頂点 \(v\) の \(2^k\) 個上の祖先、と定義します。

• 基底: \(up[0][v] = parent[v]\)（直属の上司）
• 漸化式: \(up[k][v] = up[k-1][up[k-1][v]]\)
  • 「\(2^k\) 上の祖先」は「\(2^{k-1}\) 上の祖先の、さらに \(2^{k-1}\) 上の祖先」

例えば \(N = 8\) なら \(\log_2 8 = 3\) なので、\(k = 0, 1, 2, 3\) の4段分のテーブルを作ります。

2. 深さの計算

BFS で根（社員1）からの各頂点の深さを求めます。

3. LCA の求め方（クエリ処理）

社員 \(u\) と \(v\) の LCA を求める手順：

ステップ1: 深さを揃える - \(depth[u] > depth[v]\) なら \(u\) の方が深いので、\(u\) を \(depth[u] - depth[v]\) だけ上に移動させます。 - この移動をダブリングで行います。差を二進表現し、ビットが立っている桁 \(k\) に対して \(u = up[k][u]\) とジャンプします。

ステップ2: 同時に上へ移動 - \(u = v\) ならそれが LCA です。 - そうでなければ、\(k\) を大きい方から試し、\(up[k][u] \neq up[k][v]\) ならば両方を \(2^k\) だけ上に移動します。 - 最終的に \(u\) と \(v\) は LCA の1つ下に位置するので、\(up[0][u]\) が LCA です。

具体例: 以下の木で社員5と社員6のLCAを求める場合

        1 (深さ0)
       / \
      2   3 (深さ1)
     / \
    4   5 (深さ2)
   /
  6 (深さ3)

• \(depth[6] = 3\), \(depth[5] = 2\) → 差は1なので、6を1つ上に移動 → 頂点4
• \(4 \neq 5\) → 上を見ると \(up[0][4] = 2\), \(up[0][5] = 2\) で一致 → LCA は 2

計算量

• 時間計算量: 前処理 \(O(N \log N)\)、各クエリ \(O(\log N)\)、全体 \(O((N + Q) \log N)\)
• 空間計算量: \(O(N \log N)\)（ダブリングテーブル）

実装のポイント

• LOG の設定: N.bit_length() で \(\lceil \log_2 N \rceil + 1\) 程度を取ると安全です。

• 根（社員1）の親: \(up[k][1] = 0\)（存在しない頂点）としておくと、根を超えてジャンプしても安全に処理できます。

• 高速入力: Python では sys.stdin.buffer.read() でまとめて読み込むことで入出力のボトルネックを軽減しています。

• 出力のまとめ書き: クエリごとに print するのではなく、リストに溜めて最後に '\n'.join(out) で一括出力することで高速化しています。

  ソースコード

import sys
from math import log2

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    parent = [0] * (N + 1)
    for i in range(2, N + 1):
        parent[i] = int(input_data[idx]); idx += 1
    
    LOG = max(1, (N).bit_length())
    
    # Binary lifting table
    up = [[0] * (N + 1) for _ in range(LOG)]
    for i in range(1, N + 1):
        up[0][i] = parent[i]
    
    for k in range(1, LOG):
        for i in range(1, N + 1):
            up[k][i] = up[k-1][up[k-1][i]]
    
    # Compute depth using BFS
    depth = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        children[parent[i]].append(i)
    
    from collections import deque
    queue = deque([1])
    visited = [False] * (N + 1)
    visited[1] = True
    while queue:
        u = queue.popleft()
        for v in children[u]:
            if not visited[v]:
                visited[v] = True
                depth[v] = depth[u] + 1
                queue.append(v)
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for k in range(LOG):
            if (diff >> k) & 1:
                u = up[k][u]
        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):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        out.append(str(lca(x, y)))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。