Company Queries II

import math

n, q = map(int, input().split())
maxLog = int(math.ceil(math.log2(n))) + 1
up = [[0] * maxLog for _ in range(n + 1)]
depth = [0] * (n + 1)
parent = [0, 0] + list(map(int, input().split()))

depth[1] = 0
for i in range(2, n + 1):
    depth[i] = depth[parent[i]] + 1

for i in range(1, n + 1):
    up[i][0] = parent[i]

for k in range(1, maxLog):
    for node in range(1, n + 1):
        up[node][k] = up[up[node][k-1]][k-1]

def ancestor(x, k):
    for i in range(maxLog):
        if k & (1 << i):
            x = up[x][i]
            if x == 0:
                return 0
    return x

def lca(a, b):
    if depth[a] < depth[b]:
        a, b = b, a
    a = ancestor(a, depth[a] - depth[b])
    if a == b:
        return a
    for k in range(maxLog - 1, -1, -1):
        if up[a][k] != up[b][k]:
            a = up[a][k]
            b = up[b][k]
    return up[a][0]

for _ in range(q):
    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