Company Queries II

import math
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def dfs(v, d):
    global g, nd, r
    nd.append((v, d))
    if r[v] == -1:
        r[v] = len(nd)-1
    for w in g[v]:
        dfs(w, d + 1)
        nd.append((v, d))
 
 
def build_tree_min():
    global nd, min_tree, k
    for i in range(m):
        min_tree[k + i] = (nd[i][1], i)
    for i in range(k - 1, 0, -1):
        min_tree[i] = min(min_tree[2 * i], min_tree[2 * i + 1])
 
 
def answer_min(a, b):
    global min_tree, k
    res = (math.inf, -1)
    a += k
    b += k
    while a <= b:
        if a % 2 == 1:
            res = min(res, min_tree[a])
            a += 1
        if b % 2 == 0:
            res = min(res, min_tree[b])
            b -= 1
        a //= 2
        b //= 2
    return res
 
 
n, q = map(int, input().split())
nd = []
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(nd)
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(nd[w][0] + 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: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED