Company Queries II

import sys 

input = sys.stdin.read().split()

n = int(input[0])
q = int(input[1])

log = 20


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

for i in range(2,n+1):
    b = int(input[i])
    up[i][0] = b
    depth[i] = depth[b] + 1

    for j in range(1,log): 
        up[i][j] = up[up[i][j-1]][j-1]


out = []
idx = n+1
for i in range(q): 
    a = int(input[idx])
    b = int(input[idx+1])
    idx +=2
    if depth[a] < depth[b]: 
        a,b = b,a

    diff = depth[a] - depth[b] 
    for j in range(log) : 
        if (diff >> j) & 1: 
            a = up[a][j]

    if a ==b : 
        out.append(str(a))
        continue

    for j in range(log -1, -1, -1):
        if up[a][j] != up[b][j]:
            a = up[a][j]
            b = up[b][j]

    out.append(str(up[a][0]))

sys.stdout.write('\n'.join(out) + '\n')

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: TIME LIMIT EXCEEDED