Company Queries II

import sys

input = sys.stdin.readline

def I():  return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def S():  return input().strip()

def lifting(par, LOG=18):  # up[j][v] = 2^j-th boss of v (0 = none), 2^18 > 2e5
    up = [par]
    for _ in range(LOG - 1):
        p = up[-1]
        up.append([p[x] for x in p])
    return up

def lca(up, dep, a, b):
    if dep[a] < dep[b]:
        a, b = b, a
    k, j = dep[a] - dep[b], 0             # 1. lift a to b's depth
    while k:
        if k & 1:
            a = up[j][a]
        k >>= 1
        j += 1
    if a == b:                            # b was a's boss
        return a
    for j in range(dep[a].bit_length() - 1, -1, -1):   # 2. biggest jumps first,
        u = up[j]
        if u[a] != u[b]:                  #    only while they stay different
            a, b = u[a], u[b]
    return up[0][a]                       # 3. both are direct reports of the answer

n, q = MI()
par = [0, 0] + LI()                       # par[v] = boss of v, root 1 has none
dep = [0] * (n + 1)
for v in range(2, n + 1):                 # boss e_v < v, so its depth is already known
    dep[v] = dep[par[v]] + 1

up = lifting(par)

data = sys.stdin.read().split()           # all q query lines at once (faster than q readlines)
out = []
for i in range(0, 2 * q, 2):
    out.append(lca(up, dep, int(data[i]), int(data[i + 1])))
print("\n".join(map(str, out)))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED