概要

この問題は、木構造において指定された2つの頂点の「最も深い共通の先祖」、一般に LCA (Lowest Common Ancestor / 最小共通祖先) と呼ばれる頂点を求める問題です。

社員を頂点、直属の上司との関係を辺とみなすと、社長を根とする「根付き木」になります。「最も深い共通の上司」とは、2つの頂点から根に向かって遡ったときに最初に合流する頂点のことです。

考察

素朴な方法とその限界

各クエリ \((X, Y)\) に対して、以下のような手順で答えを探すことが考えられます。 1. \(X\) から根まで順番に遡り、通った頂点を記録する。 2. \(Y\) から根まで順番に遡り、最初に「手順1で記録した頂点」に到達したら、それが答え。

しかし、この方法では1回のクエリにつき最悪で \(O(N)\) の時間がかかります。クエリ数が \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となり、今回の制約（\(N=3 \times 10^5, Q=5 \times 10^4\)）では実行時間制限に間に合いません。

効率的な解決策：ダブリング

「1段ずつ遡る」のが遅い原因なので、「一気に何段も飛び越えて遡る」 仕組みを導入します。これには ダブリング という手法が有効です。

各社員について、「1代上の上司」「2代上の上司」「4代上の上司」……というように、\(2^k\) 代上の上司の情報をあらかじめ計算しておきます。これにより、どんなに離れた先祖でも \(O(\log N)\) 回のジャンプで到達できるようになります。

アルゴリズム

1. 前準備（深さとダブリングテーブルの計算）

まず、各頂点の 深さ（根からの距離）と、1代上の上司 (\(2^0\) 代上) を記録します。 制約 \(P_i < i\) により、社員番号の小さい順に処理すれば、上司の深さが確定した状態で部下の深さを計算できます。

次に、以下の関係式を用いてダブリングテーブル up[k][i]（頂点 \(i\) の \(2^k\) 代上の上司）を埋めます。 - up[k][i] = up[k-1][up[k-1][i]] - 「\(2^k\) 代上の上司」は、「\(2^{k-1}\) 代上の上司」のさらに「\(2^{k-1}\) 代上の上司」であるという性質を利用します。

2. LCAの計算（クエリ処理）

2つの頂点 \(u, v\) の LCA を以下のステップで求めます。

1. 深さを揃える: \(u\) と \(v\) のうち深い方を、ダブリングテーブルを使って浅い方の深さまで引き上げます。
2. 一致確認: 引き上げた結果 \(u = v\) になれば、それが LCA です。
3. 共に遡る: \(u\) と \(v\) が一致しない間、大きなジャンプ（\(2^k\) 代上）から順に「遡った先が一致しないならジャンプする」という操作を繰り返します。
   • 一致しないギリギリの高さまで二人で登っていくイメージです。
4. 答えの出力: 最終的な \(u\) の「1代上の上司」が LCA となります。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • ダブリングテーブルの構築に \(O(N \log N)\)。
  • 各クエリに \(O(\log N)\) かかり、全体で \(O(Q \log N)\)。
  • \(N, Q\) の大きさに対して十分に高速です。
• 空間計算量: \(O(N \log N)\)
  • \(2^k\) 代上の情報を保持するテーブルのサイズです。

実装のポイント

• 高速な入出力: Pythonの場合、データ量が多いときは sys.stdin.read().split() などを使って一括で読み込むと実行時間を短縮できます。

• 再帰制限: 木の深さが深い場合、再帰による探索（DFS）は RecursionError を起こす可能性があります。今回は \(P_i < i\) という性質を利用してループで処理していますが、一般的な木の場合は注意が必要です。

• ビット演算: 深さを揃える際や \(2^k\) の計算には、ビット演算（>>, &）を使うとスマートに記述できます。”`

  ソースコード

import sys

# 競技プログラミングのエキスパートとして、最も深い共通の上司（LCA: Lowest Common Ancestor）を
# 求めるための効率的なアルゴリズムである「ダブリング（Binary Lifting）」を用いて実装します。

def solve():
    # 高速な入出力のために sys.stdin.read().split() を使用します
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: 社員数, Q: 問い合わせ数
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # parent_0[i] は社員 i の直属の上司（1段階上）
    # depth[i] は社員 i の根（社長）からの深さ
    parent_0 = [0] * (N + 1)
    depth = [0] * (N + 1)
    
    # 社員 1 は社長（根）
    parent_0[1] = 1
    depth[1] = 0
    
    # P_i (社員 i の直属の上司) を読み込む
    # P_i < i という制約があるため、i=2から順に計算することで深さを正しく求められます
    for i in range(2, N + 1):
        p = int(input_data[i])
        parent_0[i] = p
        depth[i] = depth[p] + 1
        
    # ダブリングテーブルの作成: up[k][i] は社員 i の 2^k 代上の上司
    # N が 3*10^5 の場合、LOG は 19 程度になります
    LOG = N.bit_length()
    up = [parent_0]
    for k in range(1, LOG):
        prev_up = up[-1]
        # リスト内包表記を使用して高速にテーブルを埋めます
        # up[k][i] = up[k-1][up[k-1][i]]
        curr_up = [prev_up[prev_up[i]] for i in range(N + 1)]
        up.append(curr_up)
        
    # クエリの処理
    results = []
    # 全てのクエリデータを整数に変換して高速にアクセスできるようにします
    queries = list(map(int, input_data[N+1:]))
    
    # 逆順の範囲を事前に作成してループのオーバーヘッドを減らします
    rev_log_range = list(range(LOG - 1, -1, -1))
    
    it = iter(queries)
    for u, v in zip(it, it):
        # 1. 深い方の頂点 u を v と同じ深さまで引き上げる
        if depth[u] < depth[v]:
            u, v = v, u
        
        diff = depth[u] - depth[v]
        k = 0
        while diff:
            if diff & 1:
                u = up[k][u]
            diff >>= 1
            k += 1
        
        # 2. 引き上げた結果、同じ頂点になればそれが LCA
        if u == v:
            results.append(u)
            continue
        
        # 3. u と v が異なる間、できるだけ大きく（2^k）上に引き上げる
        for k in rev_log_range:
            up_k = up[k]
            if up_k[u] != up_k[v]:
                u = up_k[u]
                v = up_k[v]
        
        # 4. 最終的に u と v の直属の上司が LCA となる
        results.append(up[0][u])
        
    # 全ての回答をまとめて出力します
    sys.stdout.write("\n".join(map(str, results)) + "\n")

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。