Overview

This problem asks you to find the “deepest common ancestor” of two specified vertices in a tree structure, generally known as the LCA (Lowest Common Ancestor).

If we consider employees as vertices and the relationship with their direct supervisor as edges, we obtain a “rooted tree” with the president as the root. The “deepest common supervisor” is the vertex where the paths from the two vertices toward the root first converge.

Analysis

Naive Approach and Its Limitations

For each query \((X, Y)\), the following procedure could be used to find the answer: 1. Traverse upward from \(X\) to the root, recording all visited vertices. 2. Traverse upward from \(Y\) to the root, and as soon as you reach a “vertex recorded in step 1”, that is the answer.

However, this method takes \(O(N)\) time per query in the worst case. Since there are \(Q\) queries, the overall time complexity is \(O(NQ)\), which will not fit within the time limit under the given constraints (\(N=3 \times 10^5, Q=5 \times 10^4\)).

Efficient Solution: Binary Lifting

The reason for the slowness is “climbing one level at a time”, so we introduce a mechanism to “skip many levels at once”. The technique called binary lifting (doubling) is effective for this.

For each employee, we precompute the ancestor \(2^k\) levels above: “the supervisor 1 level up”, “the supervisor 2 levels up”, “the supervisor 4 levels up”, and so on. This allows us to reach any ancestor in \(O(\log N)\) jumps, no matter how far away it is.

Algorithm

1. Preprocessing (Computing Depths and the Binary Lifting Table)

First, record the depth (distance from the root) of each vertex and the direct supervisor (\(2^0\) levels up). Due to the constraint \(P_i < i\), processing employees in increasing order of their ID ensures that the supervisor’s depth is already determined when computing a subordinate’s depth.

Next, fill in the binary lifting table up[k][i] (the ancestor \(2^k\) levels above vertex \(i\)) using the following recurrence: - up[k][i] = up[k-1][up[k-1][i]] - This utilizes the property that “the ancestor \(2^k\) levels up” is “the ancestor \(2^{k-1}\) levels up from the ancestor \(2^{k-1}\) levels up”.

2. Computing LCA (Query Processing)

The LCA of two vertices \(u, v\) is found through the following steps:

1. Equalize depths: Using the binary lifting table, raise the deeper of \(u\) and \(v\) to the same depth as the shallower one.
2. Check for match: If after raising we have \(u = v\), then that is the LCA.
3. Climb together: While \(u\) and \(v\) are not equal, starting from the largest jump (\(2^k\) levels up), repeat the operation: “if the ancestors after jumping are not the same, then jump.”
   • Think of it as both vertices climbing up to just below the point where they would meet.
4. Output the answer: The “direct supervisor (1 level up)” of the final \(u\) is the LCA.

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Building the binary lifting table takes \(O(N \log N)\).
  • Each query takes \(O(\log N)\), so all queries together take \(O(Q \log N)\).
  • This is sufficiently fast for the given sizes of \(N\) and \(Q\).
• Space complexity: \(O(N \log N)\)
  • This is the size of the table storing the \(2^k\)-th ancestor information.

Implementation Notes

• Fast I/O: In Python, when the amount of data is large, reading all input at once using sys.stdin.read().split() can reduce execution time.

• Recursion limit: If the tree is deep, recursive traversal (DFS) may cause a RecursionError. In this problem, we leverage the property \(P_i < i\) to process using loops, but care is needed for general trees.

• Bit operations: When equalizing depths or computing \(2^k\), using bitwise operations (>>, &) allows for clean and concise code.

  Source Code

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()

---

This editorial was generated by gemini-3-flash-thinking.