Company Queries II

import sys
inp = sys.stdin.read().split()
n = int(inp[0])
q=int(inp[1])


maxpower = 18 #set maxpower to 18 for preprocessing since in the worst case n = 200 000 which is 2^17.., 
up = [[0] * (n + 1) for _ in range(maxpower)] #stores for each employee, his superior at leevel k if there is one
depth = [0]*(n+1)

tracker = 2
for i in range(2,n+1):
    boss = int(inp[i])
    up[0][i] = boss 
    depth[i] = depth[boss] +1    
    tracker+=1

for j in range(1, maxpower):
        prev_level = up[j-1] 
        curr_level = up[j]
        for i in range(1, n + 1):        
            curr_level[i] = prev_level[prev_level[i]]

#now we need to find the lowest common ancestors for each query



def get_lca(a,b):
    if depth[a] < depth[b]:
        a, b = b, a

    #once we have the deeper node, we gotta make sure they're on the same level
    diff = depth[a] - depth[b]

    for j in range(maxpower):
            #for each jump (power of 2) , shift the bits to check if the bit is activated. if it is we jump by that much
            #goal here is to bring a up to the same level as b
            if (diff >> j) & 1:
                a = up[j][a]
    if a == b:
         return a
    for j in range(maxpower-1,-1,-1):
         if up[j][a] != up[j][b] :
             a = up[j][a]
             b = up[j][b]

    return up[0][a]

    #now we're gonna make both nnodes climb until we found a 

output = []
for _ in range(q):
    a = int(inp[tracker])
    b = int(inp[tracker+1])
    tracker+=2
    output.append(str(get_lca(a,b)))
sys.stdout.write('\n'.join(output) + '\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