Overview

The “deepest common supervisor shared by two people” asked for in each query is exactly the LCA (Lowest Common Ancestor) in a tree.
To process this efficiently, we precompute ancestors using Binary Lifting (Doubling) and answer each query in \(O(\log N)\).

Analysis

This problem can be modeled as a rooted tree (with root 1), where employees are vertices and direct supervisor relationships are edges.
The “deepest common supervisor” of employees \(X\) and \(Y\) is precisely the LCA in the tree.

Why a naive approach is too slow

For example, if for each query we: - Traverse all ancestors of \(X\) - Walk upward from \(Y\) to find the first matching ancestor

this takes \(O(N)\) per query in the worst case.
Since \(Q\) is up to \(5 \times 10^4\) and \(N\) is up to \(3 \times 10^5\), an \(O(NQ)\) approach will not be fast enough.

How to speed it up

We use binary lifting, a standard technique for LCA.
For each vertex \(v\), we precompute:

• up[0][v] = the parent 1 level above
• up[1][v] = the ancestor 2 levels above
• up[2][v] = the ancestor 4 levels above
• …
• up[k][v] = the ancestor \(2^k\) levels above

With this precomputation,
both “closing the depth gap” and “moving both nodes upward simultaneously” can be done bit by bit, resulting in \(O(\log N)\) per query.

Algorithm

1. Precomputation (depth and parent)

   • Due to the input condition \(P_i < i\), processing vertices 2..N in order guarantees that each parent’s information is already determined.
   • Compute depth as depth[v] = depth[parent] + 1.
   • Set up[0][v] = parent.
   • For root 1, set up[0][1] = 1 (as a sentinel, making it its own parent).

2. Building the binary lifting table

   • up[k][v] = up[k-1][ up[k-1][v] ]
   • This gives us the \(2^k\)-th ancestor.

3. LCA query

   • Let b be the shallower node and a be the deeper node (swap if necessary).
   • Compute the depth difference d = depth[a] - depth[b], and for each set bit in d, apply a = up[bit][a] to close the gap.
   • If a == b at this point, that is the LCA (the case where one node is an ancestor of the other).
   • Otherwise, iterate k from the largest value downward: when up[k][a] != up[k][b], move both nodes upward simultaneously.
   • Finally, the parent one level above, up[0][a], is the LCA.

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
• Space complexity: \(O(N \log N)\)

Implementation Notes

• Use LOG = N.bit_length() to determine the required number of levels (approximately \(\lceil \log_2 N \rceil\)).

• Setting the root’s parent to 1 helps prevent out-of-bounds array access and makes the implementation more robust.

• In this code, DFS/BFS is not needed to compute depths (leveraging the property \(P_i < i\)).

• Collecting output in a list and printing with "\n".join(out) at the end is faster.

  Source Code

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

This editorial was generated by gpt-5.3-codex.