Company Queries II

from collections import deque

n, queries = map(int, input().split())

if n == 1:
    for _ in range(queries):
        input()
        print(1)
    exit()

children = [[] for _ in range(n + 1)]
bosses = list(map(int, input().split()))
for i, boss in enumerate(bosses, 2):
    children[boss].append(i)

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

queue = deque([1])
depth[1] = 0
ancestor[1][0] = 1

while queue:
    node = queue.popleft()
    for child in children[node]:
        depth[child] = depth[node] + 1
        ancestor[child][0] = node
        queue.append(child)

for i in range(1, LOG):
    for node in range(1, n + 1):
        ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1]


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 >> i) & 1:
            a = ancestor[a][i]

    if a == b:
        return a

    for i in range(LOG - 1, -1, -1):
        if ancestor[a][i] != ancestor[b][i]:
            a = ancestor[a][i]
            b = ancestor[b][i]

    return ancestor[a][0]


for _ in range(queries):
    a, b = map(int, input().split())
    print(lca(a, b))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED