概要

各クエリで求める「2人に共通する最も深い上司」は、木における LCA（Lowest Common Ancestor: 最小共通祖先） そのものです。
これを高速に処理するために、ダブリング（Binary Lifting） で祖先を前計算して、各クエリを \(O(\log N)\) で解きます。

考察

この問題は、社員を頂点・直属の上司関係を辺とした根付き木（根は 1）です。
社員 \(X, Y\) の「共通の上司のうち最も深いもの」は、まさに木の LCA です。

素朴解が厳しい理由

例えば各クエリごとに - \(X\) の祖先を全部たどる - \(Y\) を上にたどって最初に一致する点を探す

のようにすると、最悪で 1 クエリあたり \(O(N)\) かかります。
\(Q\) は最大 \(5 \times 10^4\)、\(N\) は最大 \(3 \times 10^5\) なので、\(O(NQ)\) は間に合いません。

どう高速化するか

LCA の定番手法であるダブリングを使います。
各頂点 \(v\) について

• up[0][v] = 1 個上の親
• up[1][v] = 2 個上の祖先
• up[2][v] = 4 個上の祖先
• …
• up[k][v] = \(2^k\) 個上の祖先

を前計算しておけば、
「深さ差を埋める」「同時に上へ上げる」がどちらもビット単位ででき、1 クエリ \(O(\log N)\) になります。

アルゴリズム

1. 前計算（深さと親）

   • 入力条件 \(P_i < i\) のため、頂点 2..N を順に見れば親の情報は既に確定済み。
   • depth[v] = depth[parent] + 1 で深さを計算。
   • up[0][v] = parent を設定。
   • 根 1 は up[0][1] = 1 としておく（番兵的に自分を親にする）。

2. ダブリング表の構築

   • up[k][v] = up[k-1][ up[k-1][v] ]
   • これで \(2^k\) 先祖が求まる。

3. LCA クエリ

   • 深さが浅い方を b、深い方を a とする（必要なら swap）。
   • 深さ差 d = depth[a] - depth[b] を、d の立っているビットごとに a = up[bit][a] して埋める。
   • ここで a == b なら、それが LCA（片方がもう片方の祖先のケース）。
   • 違う場合、k を大きい方から下げながら、 up[k][a] != up[k][b] のとき両方を同時に上げる。
   • 最後に 1 個上の親 up[0][a] が LCA。

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
• 空間計算量: \(O(N \log N)\)

実装のポイント

• LOG = N.bit_length() で必要な段数（おおよそ \(\lceil \log_2 N \rceil\)）を確保。

• 根の親を 1 にしておくと、配列外参照を防ぎやすく実装が安定します。

• このコードでは DFS/BFS 不要で深さを作れます（P_i < i の性質を利用）。
  

• 出力は list にためて最後に "\n".join(out) すると高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    P = [0] + [0] + list(map(int, input().split()))  # P[i] for i>=2

    LOG = (N).bit_length()

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

    up[0][1] = 1
    for v in range(2, N + 1):
        p = P[v]
        up[0][v] = p
        depth[v] = depth[p] + 1

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

    def lca(a, b):
        if depth[a] < depth[b]:
            a, b = b, a

        d = depth[a] - depth[b]
        bit = 0
        while d:
            if d & 1:
                a = up[bit][a]
            d >>= 1
            bit += 1

        if a == b:
            return a

        for k in range(LOG - 1, -1, -1):
            if up[k][a] != up[k][b]:
                a = up[k][a]
                b = up[k][b]

        return up[0][a]

    out = []
    for _ in range(Q):
        x, y = map(int, input().split())
        out.append(str(lca(x, y)))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。