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 = [[0 for _ in range(2*len(visited[0]))] for _ in range(2)]
for i in range(len(visited[0])):
    min_queries[0][len(visited[0]) + i] = visited[0][i]
    min_queries[1][len(visited[0]) + i] = visited[1][i]
for i in range(len(visited[0])-1, 0, -1):
    if min_queries[1][2*i] < min_queries[1][2*i+1]:
        min_queries[1][i] = min_queries[1][2*i]
        min_queries[0][i] = min_queries[0][2*i]
    else:
        min_queries[1][i] = min_queries[1][2*i+1]
        min_queries[0][i] = min_queries[0][2*i+1]

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

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: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED