Company Queries II

n, q = map(int, input().split())
boss = [0, 0] + list(map(int, input().split()))

children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
    children[boss[i]].append(i)

depth = [0] * (n + 1)


def dfs(node, d):
    depth[node] = d
    for child in children[node]:
        dfs(child, d + 1)


dfs(1, 0)

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

for i in range(1, n + 1):
    up[i][0] = boss[i]

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

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

    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[a][i]

    if a == b:
        print(a)
        continue

    for i in range(LOG - 1, -1, -1):
        if up[a][i] != up[b][i]:
            a = up[a][i]
            b = up[b][i]

    print(up[a][0])

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 17, in <module>
    dfs(1, 0)
  File "input/code.py", line 14, in dfs
    dfs(child, d + 1)
  File "input/code.py", line 14, in dfs
    dfs(child, d + 1)
  File "input/code.py", line 14, in dfs
    dfs(child, d + 1)
  [Previous line repeated 1576 more times]
  File "input/code.py", line 12, in dfs
    depth[node] = d
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 17, in <module>
    dfs(1, 0)
  File "input/code.py", line 14, in dfs
    dfs(child, d + 1)
  File "input/code.py", line 14, in dfs
    dfs(child, d + 1)
  File "input/code.py", line 14, in dfs
    dfs(child, d + 1)
  [Previous line repeated 1582 more times]
  File "input/code.py", line 12, in dfs
    depth[node] = d
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 17, in <module>
    dfs(1, 0)
  File "input/code.py", line 14, in dfs
    dfs(child, d + 1)
  File "input/code.py", line 14, in dfs
    dfs(child, d + 1)
  File "input/code.py", line 14, in dfs
    dfs(child, d + 1)
  [Previous line repeated 1576 more times]
  File "input/code.py", line 12, in dfs
    depth[node] = d
RecursionError: maximum recursion depth exceeded