Overview

This problem asks us to find the “deepest common supervisor of two employees” multiple times on a rooted tree.
This is a classic problem of finding the LCA (Lowest Common Ancestor) in a tree, which can be efficiently solved using binary lifting (doubling).

Analysis

What we want to find is the deepest employee who is a supervisor of both employees \(X\) and \(Y\).
In terms of tree structure, this corresponds exactly to the LCA of \(X\) and \(Y\).

Naive Approach

For example, for each query we could:

• Lift the deeper vertex upward to match the depths
• Then move both vertices up to their parent one step at a time

This method does give the correct answer.

However, in the worst case, each query takes \(O(N)\) time.
The constraints are:

• \(N \le 3 \times 10^5\)
• \(Q \le 5 \times 10^4\)

So the worst case becomes \(O(NQ)\), which is too slow.

Key Insight

Instead of “traversing parents one at a time,”
if we precompute the ancestor \(2^0, 2^1, 2^2, \dots\) levels above, we can jump upward all at once.

For example, if we store:

• up[0][v]: the parent 1 level above vertex \(v\)
• up[1][v]: the ancestor 2 levels above vertex \(v\)
• up[2][v]: the ancestor 4 levels above vertex \(v\)
• …

then we can decompose the depth difference in binary and fill it in \(O(\log N)\) time.

Furthermore, after matching the depths, by trying large jumps first and working downward, we can quickly approach just below the LCA.

A Nice Property of This Problem

The input guarantees \(P_i < i\).
This means the parent of employee \(i\) always has a smaller index, so if we process from \(2\) onward:

• The parent’s depth is already known
• Therefore we can immediately compute depth[i] = depth[p] + 1

This is a useful property.
Because of this, the code computes depths without using DFS or BFS.

Algorithm

1. Precomputation

For each vertex, we compute:

• depth[v]: depth from the root
• up[j][v]: the ancestor \(2^j\) levels above vertex \(v\)

First, from the parent information:

• up[0][i] = P_i
• depth[i] = depth[P_i] + 1

Next, we fill the doubling table using:

\(up[j][v] = up[j-1][\,up[j-1][v]\,]\)

This is natural if you think of it as: “the ancestor \(2^j\) levels above is the ancestor \(2^{j-1}\) levels above the ancestor that is already \(2^{j-1}\) levels above.”

---

2. Processing Each Query

For a query \((x, y)\), we find the LCA.

Step 1: Match the Depths

First, lift the deeper vertex upward so that \(x\) and \(y\) are at the same depth.

For example, if the depth difference is 13:

\(13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0\)

So we jump:

• 8 levels up
• 4 levels up
• 1 level up

Using the doubling table, this takes \(O(\log N)\).

Step 2: Check if They Already Match

If \(x = y\) after matching the depths, that vertex is the answer.
This corresponds to the case where “one employee was already a supervisor of the other.”

Step 3: Lift Both Vertices Simultaneously

If they are still different, we examine jumps from largest to smallest.

Looking at \(j\) from large to small:

• If up[j][x] != up[j][y]

then we are still below the LCA, so we lift both to that ancestor.

After repeating this, \(x\) and \(y\) end up as children directly below the LCA.
Therefore, the answer is up[0][x] (or equivalently up[0][y]).

---

Concrete Example

Consider the following tree:

• \(1\) is the root
• The parent of \(2, 3\) is \(1\)
• The parent of \(4, 5\) is \(2\)
• The parent of \(6, 7\) is \(3\)

Then:

• \(LCA(4, 5) = 2\)
• \(LCA(4, 6) = 1\)
• \(LCA(2, 5) = 2\)

In the last example, after matching the depths, \(x = y\) holds, so the answer is obtained directly.

Complexity

• Time complexity: Precomputation is \(O(N \log N)\), each query is \(O(\log N)\), for a total of \(O(N \log N + Q \log N)\)
• Space complexity: \(O(N \log N)\)

Implementation Notes

• Using LOG = N.bit_length() ensures \(2^{LOG} > N\), which guarantees enough levels.

• The root vertex \(1\) has no parent, but in this implementation 0 is used as a dummy.
  Leaving up[j][1] = 0 causes no issues.

• Since \(P_i < i\) is guaranteed in this problem, depth[i] can be computed directly in input order.

• Because the number of queries and vertices is large, sys.stdin.buffer.read() is used for fast input.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    Q = next(it)

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

    for i in range(2, N + 1):
        p = next(it)
        up[0][i] = p
        depth[i] = depth[p] + 1

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

    out = []
    for _ in range(Q):
        x = next(it)
        y = next(it)

        if depth[x] < depth[y]:
            x, y = y, x

        diff = depth[x] - depth[y]
        b = 0
        while diff:
            if diff & 1:
                x = up[b][x]
            diff >>= 1
            b += 1

        if x == y:
            out.append(str(x))
            continue

        for j in range(LOG - 1, -1, -1):
            if up[j][x] != up[j][y]:
                x = up[j][x]
                y = up[j][y]

        out.append(str(up[0][x]))

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.