Company Queries II

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])

    # par[v] = boss of v; root points to itself (index 0 is a dummy)
    par = [1] * (n + 1)
    depth = [0] * (n + 1)
    for i in range(2, n + 1):
        e = int(data[i])          # e_i is data[2 + (i-2)] = data[i]
        par[i] = e
        depth[i] = depth[e] + 1   # valid because e < i

    # only as many levels as the deepest node needs
    LOG = max(1, max(depth).bit_length())

    # up[k][v] = 2^k-th ancestor of v
    up = [par]
    for _ in range(1, LOG):
        prev = up[-1]
        up.append([prev[x] for x in prev])

    out = []
    pos = n + 1                   # queries start after the n-1 parent values
    for _ in range(q):
        a = int(data[pos])
        b = int(data[pos + 1])
        pos += 2

        if depth[a] < depth[b]:
            a, b = b, a

        # lift a to b's depth
        diff = depth[a] - depth[b]
        k = 0
        while diff:
            if diff & 1:
                a = up[k][a]
            diff >>= 1
            k += 1

        if a == b:
            out.append(a)
            continue

        # lift both as high as possible without meeting
        for k in range(LOG - 1, -1, -1):
            row = up[k]
            ua = row[a]
            ub = row[b]
            if ua != ub:
                a = ua
                b = ub
        out.append(par[a])

    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

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