Company Queries II

import sys
import math

sys.setrecursionlimit(300000)
input = sys.stdin.read
output = sys.stdout.write

def preprocess_lca(n, boss):
    LOG = math.ceil(math.log2(n))  # Dynamically calculate the log based on n
    up = [[-1] * LOG for _ in range(n + 1)]
    depth = [0] * (n + 1)
    adj = [[] for _ in range(n + 1)]

    # Build the tree structure based on the boss list
    for i in range(2, n + 1):
        adj[boss[i - 2]].append(i)

    # DFS to initialize the depth and up tables
    def dfs(v, parent):
        up[v][0] = parent
        for j in range(1, LOG):
            if up[v][j - 1] != -1:
                up[v][j] = up[up[v][j - 1]][j - 1]
        for u in adj[v]:
            if u != parent:
                depth[u] = depth[v] + 1
                dfs(u, v)

    dfs(1, -1)  # Root the tree at node 1 (general director)

    return up, depth

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

    LOG = len(up[0])

    # Lift node `a` to the same depth as node `b`
    for j in range(LOG - 1, -1, -1):
        if depth[a] - (1 << j) >= depth[b]:
            a = up[a][j]

    if a == b:
        return a

    # Binary lifting to find the LCA
    for j in range(LOG - 1, -1, -1):
        if up[a][j] != up[b][j]:
            a = up[a][j]
            b = up[b][j]

    return up[a][0]

def main():
    # Use faster input handling
    data = sys.stdin.read().split()
    
    n = int(data[0])
    q = int(data[1])
    
    # Read the boss list and queries
    boss = list(map(int, data[2:n + 1]))
    queries = data[n + 1:]

    # Preprocess to create the LCA table
    up, depth = preprocess_lca(n, boss)

    # Process the queries
    result = []
    for i in range(0, len(queries), 2):
        a = int(queries[i])
        b = int(queries[i + 1])
        result.append(str(lca(a, b, up, depth)))

    # Use fast output
    sys.stdout.write("\n".join(result) + "\n")

if __name__ == "__main__":
    main()

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