Company Queries II

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

n, q = [int(x) for x in input().split()]


ancestors = [int(x) for x in input().split()]

reverse_ancestors = [[] for _ in range(n + 1)]
for index, value in enumerate(ancestors):
    reverse_ancestors[value].append(index + 2)


depth = [0] * (n + 1)
for i in range(2, n + 1):
    depth[i] = depth[ancestors[i - 2]] + 1


L = []
nodes = []

def search(node):
    children = reverse_ancestors[node]
    L.append((depth[node], node))
    nodes.append(node)
    for child in children:
        search(child)
        L.append((depth[node], node))
        nodes.append(node)

search(1)


indexs = [-1] * (n + 1)
for index, node in enumerate(nodes):
    if indexs[node] == -1:
        indexs[node] = index


min_list = []
min_list.append(L)

m = len(L)
k = 1
while (1 << k) <= m:
    prev = min_list[k - 1]
    curr = []
    step = 1 << (k - 1)
    for i in range(0, m - (1 << k) + 1):
        curr.append(min(prev[i], prev[i + step], key=lambda x: x[0]))
    min_list.append(curr)
    k += 1



def mini(a, b):
    if b < a:
        a, b = b, a
    if a == b:
        return L[a]

    length = b - a + 1


    exp = 0
    while (1 << (exp + 1)) <= length:
        exp += 1
    power = 1 << exp

    left = min_list[exp][a]
    right = min_list[exp][b - power + 1]  
    return left if left[0] < right[0] else right


for _ in range(q):
    a, b = [int(x) for x in input().split()]
    print(mini(indexs[a], indexs[b])[1])

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 32, in <module>
    search(1)
  File "input/code.py", line 28, in search
    search(child)
  File "input/code.py", line 28, in search
    search(child)
  File "input/code.py", line 28, in search
    search(child)
  [Previous line repeated 158551 more times]
  File "input/code.py", line 24, in search
    children = reverse_ancestors[node]
RecursionError: maximum recursion depth exceeded

Test 7

Verdict: ACCEPTED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED