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

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)
for query in queries:
    a, b = query[0], query[1]
    idxA = first[a]
    idxB = first[b]
    mini = float('inf')
    nbrmini = -1
    for i in range(min(idxA,idxB), max(idxA,idxB)+1):
        if visited[1][i] < mini:
            mini = visited[1][i]
            nbrmini = visited[0][i]
    print(nbrmini+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 26, in <module>
    dfs(0,0)
  File "input/code.py", line 22, in dfs
    dfs(node, d+1)
  File "input/code.py", line 22, in dfs
    dfs(node, d+1)
  File "input/code.py", line 22, in dfs
    dfs(node, d+1)
  [Previous line repeated 1576 more times]
  File "input/code.py", line 18, in dfs
    first[x] = len(visited[0])
RecursionError: maximum recursion depth exceeded

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 26, in <module>
    dfs(0,0)
  File "input/code.py", line 22, in dfs
    dfs(node, d+1)
  File "input/code.py", line 22, in dfs
    dfs(node, d+1)
  File "input/code.py", line 22, in dfs
    dfs(node, d+1)
  [Previous line repeated 1581 more times]
  File "input/code.py", line 18, in dfs
    first[x] = len(visited[0])
RecursionError: maximum recursion depth exceeded

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 26, in <module>
    dfs(0,0)
  File "input/code.py", line 22, in dfs
    dfs(node, d+1)
  File "input/code.py", line 22, in dfs
    dfs(node, d+1)
  File "input/code.py", line 22, in dfs
    dfs(node, d+1)
  [Previous line repeated 1576 more times]
  File "input/code.py", line 18, in dfs
    first[x] = len(visited[0])
RecursionError: maximum recursion depth exceeded