Company Queries II

import sys
sys.setrecursionlimit(300000)

LOG = 18  # This is because 2^18 > 2 * 10^5

def dfs(v, p, d):
    parent[v][0] = p  # 2^0-th parent is the direct parent
    depth[v] = d
    for u in tree[v]:
        if u != p:
            dfs(u, v, d + 1)

def preprocess_lca(n):
    # Compute all 2^i ancestors for each node
    for i in range(1, LOG):
        for v in range(1, n + 1):
            if parent[v][i - 1] != -1:
                parent[v][i] = parent[parent[v][i - 1]][i - 1]

def lca(a, b):
    # Ensure that a is deeper than b
    if depth[a] < depth[b]:
        a, b = b, a

    # Lift a up until it's at the same depth as b
    for i in range(LOG - 1, -1, -1):
        if depth[a] - (1 << i) >= depth[b]:
            a = parent[a][i]

    if a == b:
        return a

    # Lift both a and b up until their parents are the same
    for i in range(LOG - 1, -1, -1):
        if parent[a][i] != parent[b][i]:
            a = parent[a][i]
            b = parent[b][i]

    return parent[a][0]

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

tree = [[] for _ in range(n + 1)]
parent = [[-1] * LOG for _ in range(n + 1)]
depth = [-1] * (n + 1)

# Construct the tree
for i in range(2, n + 1):
    boss = bosses[i - 2]
    tree[boss].append(i)
    tree[i].append(boss)

# Perform DFS to set up the parent and depth arrays
dfs(1, -1, 0)
preprocess_lca(n)

# Process the queries
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: 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