Company Queries II

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

tree = [[] for _ in range(n + 1)]
for i, b in enumerate(bosses, start=2):
    tree[b].append(i)

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


# Iterative DFS with stack
def dfs(root):
    stack = [(root, root)]  # (node, parent)
    order = []
    while stack:
        v, p = stack.pop()
        order.append((v, p))
        for nxt in tree[v]:
            if nxt != p:
                stack.append((nxt, v))

    # Process in order (parent before children)
    order.reverse()
    for v, p in order:
        up[0][v] = p
        for i in range(1, LOG):
            up[i][v] = up[i - 1][up[i - 1][v]]
        if v != p:
            depth[v] = depth[p] + 1


dfs(1)


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 & (1 << i):
            a = up[i][a]

    if a == b:
        return a

    for i in reversed(range(LOG)):
        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: WRONG ANSWER

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

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