Company Queries II

import sys

max_log = 18
n, q = [int(x) for x in input().split()]
 
sys.setrecursionlimit(10**7)

ancestors = [[0 for _ in range(max_log)] for _ in range(n+1)] #ancestor[i][j] = 2**jth ancestor of i
depths = [0 for _ in range(n+1)]
 
GRAPH = {i:[] for i in range(n+1)}
for i, x in enumerate(input().split()):
    x = int(x)
    GRAPH[i+2].append(x)
    GRAPH[x].append(i+2)
 
def dfs(node, parent):
    ancestors[node][0] = parent
    for i in range(max_log):
        if ancestors[node][i-1] != 0:
            ancestors[node][i] = ancestors[ancestors[node][i-1]][i-1]
    for adj in GRAPH[node]:
        if adj != parent:
            depths[adj] = depths[node] + 1
            dfs(adj, node)
 
dfs(1, 0)
 
def res(a, b):
    if depths[a] < depths[b]:
        a, b = b, a
    
    diff = depths[a] - depths[b]
    for i in range(max_log):
        if (diff >> i) & 1:
            a = ancestors[a][i]
 
    if a == b:
        return a
 
    for i in range(max_log-1, -1, -1):
        if ancestors[a][i] != ancestors[b][i]:
            a = ancestors[a][i]
            b = ancestors[b][i]
    return ancestors[a][0]
 
sol = []
for _ in range(q):
    a, b = [int(x) for x in input().split()]
    sol.append(res(a, b))
 
for elt in sol:
    print(elt)

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: ACCEPTED

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