Company Queries II

import sys
from collections import deque

input = sys.stdin.readline

n, q = map(int, input().split())
boss = [0, 0] + list(map(int, input().split()))

adj = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
    adj[boss[i]].append(i)

LOG = 20
up = [[0] * (n + 1) for _ in range(LOG)]
depth = [0] * (n + 1)


# BFS to set depth and up[0]
def bfs(root=1):
    queue = deque([root])
    depth[root] = 0
    up[0][root] = 0
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            depth[v] = depth[u] + 1
            up[0][v] = u
            queue.append(v)


bfs()

# Precompute up table
for i in range(1, LOG):
    for v in range(1, n + 1):
        up[i][v] = up[i - 1][up[i - 1][v]]


def lca(a, b):
    if depth[a] < depth[b]:
        a, b = b, a
    diff = depth[a] - depth[b]
    for i in range(LOG):
        if diff & (1 << i):
            a = up[i][a]
    if a == b:
        return a
    for i in reversed(range(LOG)):
        if up[i][a] != up[i][b]:
            a = up[i][a]
            b = up[i][b]
    return up[0][a]


output = []
for _ in range(q):
    a, b = map(int, input().split())
    output.append(str(lca(a, b)))

print("\n".join(output))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED