Company Queries II

import math
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def dfs(v, d):
    global g, node_ids, depths, r
    node_ids.append(v)
    depths.append(d)
    r[v] = len(node_ids)-1
    for w in g[v]:
        dfs(w, d + 1)
        node_ids.append(v)
        depths.append(d)

def build_tree_min():
    global depths, min_tree, k
    for i in range(m):
        min_tree[k + i] = (depths[i], i)
    for i in range(k - 1, 0, -1):
        left, right = min_tree[2 * i], min_tree[2 * i + 1]
        if left[0] < right[0]:
            min_tree[i] = left
        else:
            min_tree[i] = right


def answer_min(a, b):
    global min_tree, k
    res = math.inf
    value = -1
    a += k
    b += k
    while a <= b:
        if a % 2 == 1:
            z, v = min_tree[a]
            if res > z:
                value = v
                res = z
            a += 1
        if b % 2 == 0:
            z, v = min_tree[b]
            if res > z:
                value = v
                res = z
            b -= 1
        a //= 2
        b //= 2
    return res, value


n, q = map(int, input().split())
node_ids = []
depths = []
g = [[] for _ in range(n)]
r = [-1] * n
x = list(map(int, input().split()))
for i in range(n - 1):
    g[x[i] - 1].append(i + 1)

dfs(0, 0)

m = len(node_ids)
k = 2 ** math.ceil(math.log(m, 2))
min_tree = [(math.inf, -1)] * (2 * k)
build_tree_min()
# print(k, min_tree)

output = []
for i in range(q):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    v, w = answer_min(min(r[a], r[b]), max(r[a], r[b]))
    output.append(str(node_ids[w] + 1))

sys.stdout.write("\n".join(output) + "\n")

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

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED