Company Queries II

import math
import sys
sys.setrecursionlimit(10**6)
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(i):
    global depths, min_tree, k, m
    if i >= k + m:
        return math.inf, -1
    if i >= k:
        min_tree[i] = (depths[i - k], i - k)
        return min_tree[i]
    d1, i1 = build_tree_min(2 * i)
    d2, i2 = build_tree_min(2 * i + 1)
    if d1 < d2:
        min_tree[i] = (d1, i1)
    else:
        min_tree[i] = (d2, i2)

    return min_tree[i]


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] * (2 * k)
build_tree_min(1)
# 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: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED