Company Queries II

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    q = int(input_data[1])
    
    # Adjacency list for building depths
    adj = [[] for _ in range(n + 1)]
    
    # Store binary lifting table: up[u][i] = 2^i-th ancestor of u
    # Max depth < 200,000, so 2^18 (262,144) is enough
    LOGN = 19
    up = [[0] * LOGN for _ in range(n + 1)]
    depth = [0] * (n + 1)
    
    ptr = 2
    for i in range(2, n + 1):
        parent = int(input_data[ptr])
        ptr += 1
        adj[parent].append(i)
        up[i][0] = parent

    # Iterative BFS to calculate depths and binary lifting table
    queue = [1]
    depth[1] = 0
    
    # Process tree level by level
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        
        # Fill binary lifting entries for node u
        for k in range(1, LOGN):
            prev = up[u][k - 1]
            if prev != 0:
                up[u][k] = up[prev][k - 1]
            else:
                up[u][k] = 0
                
        for v in adj[u]:
            depth[v] = depth[u] + 1
            queue.append(v)
            
    # LCA Query function
    def get_lca(a, b):
        if depth[a] < depth[b]:
            a, b = b, a
            
        # 1. Lift 'a' to the same depth as 'b'
        diff = depth[a] - depth[b]
        for k in range(LOGN):
            if (diff >> k) & 1:
                a = up[a][k]
                
        if a == b:
            return a
            
        # 2. Lift both nodes together until they are just below the LCA
        for k in range(LOGN - 1, -1, -1):
            if up[a][k] != up[b][k]:
                a = up[a][k]
                b = up[b][k]
                
        return up[a][0]

    out = []
    for _ in range(q):
        a = int(input_data[ptr])
        b = int(input_data[ptr + 1])
        ptr += 2
        out.append(str(get_lca(a, b)))
        
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

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

Test 8

Verdict: ACCEPTED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED