Company Queries II

import sys 

input = list(map(int,sys.stdin.read().split()))

n = input[0]
q = input[1]

log = 18


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

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

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


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

    diff = depth[a] - depth[b] 
    while diff >0:
        step = diff.bit_length() - 1
        a = up[step][a]
        diff ^= (1 << step)

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

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

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

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