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])
    
    LOGN = 18
    up = [0] * ((n + 1) * LOGN)
    depth = [0] * (n + 1)
    
    adj = [[] for _ in range(n + 1)]
    
    ptr = 2
    for i in range(2, n + 1):
        p = int(input_data[ptr])
        ptr += 1
        adj[p].append(i)
        up[i * LOGN] = p

    queue = [1]
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        
        u_offset = u * LOGN
        for k in range(1, LOGN):
            prev = up[u_offset + k - 1]
            if prev != 0:
                up[u_offset + k] = up[prev * LOGN + k - 1]
                
        for v in adj[u]:
            depth[v] = depth[u] + 1
            queue.append(v)

    out = []
    for _ in range(q):
        a = int(input_data[ptr])
        b = int(input_data[ptr + 1])
        ptr += 2
        
        if depth[a] < depth[b]:
            a, b = b, a
            
        diff = depth[a] - depth[b]
        for k in range(LOGN):
            if (diff >> k) & 1:
                a = up[a * LOGN + k]
                
        if a == b:
            out.append(str(a))
            continue
            
        for k in range(LOGN - 1, -1, -1):
            a_ancestor = up[a * LOGN + k]
            b_ancestor = up[b * LOGN + k]
            if a_ancestor != b_ancestor:
                a = a_ancestor
                b = b_ancestor
                
        out.append(str(up[a * LOGN]))
        
    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: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED