Overview

This problem asks you to find the Lowest Common Ancestor (LCA) of two vertices in a rooted tree. We use Binary Lifting (Doubling) to answer each query efficiently.

Analysis

Rephrasing the Problem

“The employee who is a superior of both employee \(X\) and employee \(Y\), and has the greatest depth” is exactly the Lowest Common Ancestor (LCA) of \(X\) and \(Y\) in the rooted tree.

Naive Approach and Its Issues

The simplest method is to trace parent pointers one at a time from both \(X\) and \(Y\) and find where they meet.

• Equalize the depths of \(X\) and \(Y\) → move the deeper one up one step at a time
• Once the depths are equal, move both up one step at a time until they coincide

In this case, a single query takes up to \(O(N)\), resulting in \(O(NQ)\) overall. With \(N = 3 \times 10^5\) and \(Q = 5 \times 10^4\), this leads to up to \(1.5 \times 10^{10}\) operations, which will TLE.

Solution: Binary Lifting (Doubling)

Instead of “tracing up one step at a time,” if we precompute “the ancestor \(2^k\) levels above,” we can jump any distance at once in \(O(\log N)\). This allows each query to be processed in \(O(\log N)\).

Algorithm

1. Preprocessing: Building the Doubling Table

Define \(up[k][v]\) = the ancestor \(2^k\) levels above vertex \(v\).

• Base case: \(up[0][v] = parent[v]\) (direct superior)
• Recurrence: \(up[k][v] = up[k-1][up[k-1][v]]\)
  • “The ancestor \(2^k\) levels above” is “the ancestor \(2^{k-1}\) levels above the ancestor \(2^{k-1}\) levels above”

For example, if \(N = 8\), then \(\log_2 8 = 3\), so we build a table with 4 levels for \(k = 0, 1, 2, 3\).

2. Computing Depths

Use BFS to compute the depth of each vertex from the root (employee 1).

3. Finding the LCA (Query Processing)

Procedure to find the LCA of employees \(u\) and \(v\):

Step 1: Equalize the depths - If \(depth[u] > depth[v]\), then \(u\) is deeper, so move \(u\) up by \(depth[u] - depth[v]\). - This movement is done using binary lifting. Express the difference in binary, and for each bit position \(k\) that is set, jump \(u = up[k][u]\).

Step 2: Move both upward simultaneously - If \(u = v\), then that is the LCA. - Otherwise, try \(k\) from largest to smallest. If \(up[k][u] \neq up[k][v]\), move both up by \(2^k\). - In the end, \(u\) and \(v\) will be positioned one level below the LCA, so \(up[0][u]\) is the LCA.

Concrete example: Finding the LCA of employee 5 and employee 6 in the following tree

        1 (depth 0)
       / \
      2   3 (depth 1)
     / \
    4   5 (depth 2)
   /
  6 (depth 3)

• \(depth[6] = 3\), \(depth[5] = 2\) → the difference is 1, so move 6 up by 1 → vertex 4
• \(4 \neq 5\) → looking above: \(up[0][4] = 2\), \(up[0][5] = 2\), which match → the LCA is 2

Complexity

• Time complexity: Preprocessing \(O(N \log N)\), each query \(O(\log N)\), overall \(O((N + Q) \log N)\)
• Space complexity: \(O(N \log N)\) (doubling table)

Implementation Notes

• Setting LOG: Using N.bit_length() to get approximately \(\lceil \log_2 N \rceil + 1\) is safe.

• Parent of the root (employee 1): Setting \(up[k][1] = 0\) (a non-existent vertex) allows safe handling even when jumping beyond the root.

• Fast input: In Python, reading all input at once with sys.stdin.buffer.read() reduces the I/O bottleneck.

• Batch output: Instead of calling print for each query, accumulate results in a list and output them all at once with '\n'.join(out) for faster performance.

  Source Code

import sys
from math import log2

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    parent = [0] * (N + 1)
    for i in range(2, N + 1):
        parent[i] = int(input_data[idx]); idx += 1
    
    LOG = max(1, (N).bit_length())
    
    # Binary lifting table
    up = [[0] * (N + 1) for _ in range(LOG)]
    for i in range(1, N + 1):
        up[0][i] = parent[i]
    
    for k in range(1, LOG):
        for i in range(1, N + 1):
            up[k][i] = up[k-1][up[k-1][i]]
    
    # Compute depth using BFS
    depth = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        children[parent[i]].append(i)
    
    from collections import deque
    queue = deque([1])
    visited = [False] * (N + 1)
    visited[1] = True
    while queue:
        u = queue.popleft()
        for v in children[u]:
            if not visited[v]:
                visited[v] = True
                depth[v] = depth[u] + 1
                queue.append(v)
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for k in range(LOG):
            if (diff >> k) & 1:
                u = up[k][u]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u = up[k][u]
                v = up[k][v]
        return up[0][u]
    
    out = []
    for _ in range(Q):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        out.append(str(lca(x, y)))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.