Company Queries II

import heapq

n, q  = [int(x) for x in input().split()]
boss = [int(x) for x in input().split()]
queries = []
for _ in range(q):
    a, b = [int(x) for x in input().split()]
    queries.append([a-1, b-1])

treeFromDown = [0 for _ in range(n)]
treeFromUp = [[] for _ in range(n)]
for i in range(1, n):
    treeFromDown[i] = boss[i-1]-1
    treeFromUp[boss[i-1]-1].append(i)

def howManyLevelUp(x, y):
    levelX = 0
    xFound = False
    levelY = 0
    yFound = False
    heap = [(0,0)]

    while not xFound or not yFound:
        node, level = heapq.heappop(heap)
        if node == x:
            levelX = level
            xFound = True
        if node == y:
            levelY = level
            yFound = True
        
        for child in treeFromUp[node]:
            heapq.heappush(heap, (child, level+1))
    
    return levelX, levelY

for query in queries:
    a, b = query[0], query[1]
    levelA, levelB = howManyLevelUp(a, b)
    if levelA > levelB:
        for _ in range(levelA-levelB):
            a = treeFromDown[a]
    elif levelB > levelA:
        for _ in range(levelB-levelA):
            b = treeFromDown[b]

    while a != b:
        a = treeFromDown[a]
        b = treeFromDown[b]
    
    print(a+1)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED