Company Queries II

def dfs(v, p):
    up[0][v] = p
    for u in adj[v]:
        if u != p:
            depth[u] = depth[v] + 1
            dfs(u, v)


def lca(a, b):
    if depth[a] < depth[b]:
        a, b = b, a
    diff = depth[a] - depth[b]
    for i in range(LOG):
        if diff & (1 << i):
            a = up[i][a]
    if a == b:
        return a
    for i in reversed(range(LOG)):
        if up[i][a] != up[i][b]:
            a = up[i][a]
            b = up[i][b]
    return up[0][a]


if __name__ == "__main__":
    n, q = map(int, input().split())
    bosses = list(map(int, input().split()))

    adj = [[] for _ in range(n + 1)]
    for i, b in enumerate(bosses, start=2):
        adj[b].append(i)

    queries = []
    for _ in range(q):
        a, b = map(int, input().split())
        queries.append([a, b])

    LOG = 20
    up = [[0] * (n + 1) for _ in range(LOG)]
    depth = [0] * (n + 1)

    depth[1] = 0
    dfs(1, 0)

    for j in range(1, LOG):
        for v in range(1, n + 1):
            up[j][v] = up[j - 1][up[j - 1][v]]

    for a, b in queries:
        print(lca(a, b))

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 43, in <module>
    dfs(1, 0)
  File "input/code.py", line 6, in dfs
    dfs(u, v)
  File "input/code.py", line 6, in dfs
    dfs(u, v)
  File "input/code.py", line 6, in dfs
    dfs(u, v)
  [Previous line repeated 1576 more times]
  File "input/code.py", line 2, in dfs
    up[0][v] = p
RecursionError: maximum recursion depth exceeded

Test 7

Verdict: ACCEPTED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 43, in <module>
    dfs(1, 0)
  File "input/code.py", line 6, in dfs
    dfs(u, v)
  File "input/code.py", line 6, in dfs
    dfs(u, v)
  File "input/code.py", line 6, in dfs
    dfs(u, v)
  [Previous line repeated 1582 more times]
  File "input/code.py", line 2, in dfs
    up[0][v] = p
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 43, in <module>
    dfs(1, 0)
  File "input/code.py", line 6, in dfs
    dfs(u, v)
  File "input/code.py", line 6, in dfs
    dfs(u, v)
  File "input/code.py", line 6, in dfs
    dfs(u, v)
  [Previous line repeated 1576 more times]
  File "input/code.py", line 2, in dfs
    up[0][v] = p
RecursionError: maximum recursion depth exceeded