Company Queries II

n, q = map(int, input().split())
parent = [0, 0] + list(map(int, input().split()))

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

for i in range(1, n + 1):
    up[0][i] = parent[i]

for i in range(2, n + 1):
    depth[i] = depth[parent[i]] + 1

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


def lca(a, b):
    if depth[a] < depth[b]:
        a, b = b, a

    diff = depth[a] - depth[b]
    for i in range(LOG):
        if (diff >> i) & 1:
            a = up[i][a]

    if a == b:
        return a

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

    return up[0][a]


for _ in range(q):
    a, b = map(int, input().split())
    print(lca(a, b))

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