Company Queries II

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


boss=[0] + [int(i) for i in inp[2:1+n]]
maxpower = 18 #set maxpower to 18 for preprocessing since in the worst case n = 200 000 which is 2^17.., 
up = [[0]* maxpower for _ in range(n+1)] #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[i][0] = boss 
    depth[i] += depth[boss] +1    
    tracker+=1


for j in range(1,maxpower):
    for i in range(1,n+1):        
        #i represents the employee
        #j how far up we're looking
        up[i][j] = up[up[i][j-1]][j-1]

#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[a][j]
    if a == b:
         return a
    for j in range(maxpower-1,-1,-1):
         if up[a][j] != up[b][j] :
              a = up[a][j]
              b = up[b][j]

    return up[a][0]

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

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED