Company Queries II

import sys
sys.setrecursionlimit(300000)

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])

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

visited = [[],[]]
first = [0 for _ in range(n)]
def dfs(x, d):
    global visited
    first[x] = len(visited[0])
    visited[0].append(x)
    visited[1].append(d)
    for node in tree[x]:
        dfs(node, d+1)
        visited[0].append(x)
        visited[1].append(d)
dfs(0,0)

min_queries = [(float('inf'), -1)] * (2 * len(visited[0]))
for i in range(len(visited[0])):
    min_queries[len(visited[0]) + i] = (visited[1][i], visited[0][i])
for i in range(len(visited[0])-1, 0, -1):
    min_queries[i] = min(min_queries[2*i], min_queries[2*i + 1])

def compute_minimum(a, b):
    a += len(visited[0])
    b += len(visited[0])
    res = (float('inf'), -1)
    while a <= b:
        if a%2 == 1:
            res = min(res, min_queries[a])
            a += 1
        if b%2 == 0:
            res = min(res, min_queries[b])
            b -= 1
        a //= 2
        b //= 2
    return res[1]

for query in queries:
    a, b = query[0], query[1]
    idxA = first[a]
    idxB = first[b]
    if idxA > idxB:
        idxA, idxB = idxB, idxA
    print(compute_minimum(idxA, idxB)+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: ACCEPTED

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