Company Queries II

from math import ceil, log2
from sys import setrecursionlimit

setrecursionlimit(int(1E6))

def printParentMap(parent, empCount, logHeight):
    for hh in range(logHeight):
        for ee in range(empCount):
            print(f"{parent[hh*empCount+ee]:2}", end=" ")
        print()
def run(q0, q1, bosses, heights):
    ret = -2
    if q0 == q1:
        ret = q0
    if heights[q0] == heights[q1]:
        if bosses[q0] == bosses[q1]:
            ret = bosses[q0]
        else:
            q0 = bosses[q0]
            q1 = bosses[q1]
    elif heights[q0] > heights[q1]:
        if bosses[q0] == q1:
            ret = q1
        else:
            q0 = bosses[q0]
            q1 = q1
    else:
        if q0 == bosses[q1]:
            ret = q0
        else:
            q0 = q0
            q1 = bosses[q1]
    if ret == -2:
        ret = run(q0,q1,bosses, heights)
    return ret

empCount, qCount = [int(aa) for aa in input().strip().split(" ")]
bosses = [0]+[int(aa)-1 for aa in input().strip().split(" ")]
heights = [-1]*len(bosses)
queryes = [tuple([int(aa)-1 for aa in input().strip().split(" ")]) for _ in range(qCount)]

for ii in range(len(heights)):
    kk = ii
    hh = 0
    while kk != 0:
        # print(kk,bosses[kk])
        kk = bosses[kk]
        hh += 1
    heights[ii] = hh

maxHeight = max(heights)
logHeight = ceil(log2(maxHeight + 1))

# comp = [Emp(ii, 0 if ii == 0 else bosses[ii-1]) for ii in range(empCount)]
# print(comp)
# print(bosses)
# print(heights)
# print(queryes)
for q0,q1 in queryes:
    print(run(q0, q1, bosses, heights)+1)
# bosses 

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 12

Verdict: TIME LIMIT EXCEEDED