Company Queries II

n, q = map(int, input().split())
bosses = list(map(int, input().split()))

LOG = 18

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

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

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

answers = [] 
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 j in range(LOG):
        if diff & (1 << j):
            a = up[j][a]

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

    answers.append(a)  

for x in answers: 
    print(x)

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