Company Queries II

import sys


def main():
    data = map(int, sys.stdin.buffer.read().split())
    it = iter(data)
    n = next(it)
    q = next(it)
    bosses = [next(it) for _ in range(n - 1)]

    maxk = 0
    while 2**maxk <= n:
        maxk += 1
    pre = [[0] * maxk for _ in range(n)]
    maxk -= 1

    k = 0
    while k <= maxk:
        for i in range(2, n + 1):
            if k == 0:
                pre[i - 1][k] = bosses[i - 2]
            else:
                prev = pre[i - 1][k - 1]
                pre[i - 1][k] = 0 if prev == 0 else pre[prev - 1][k - 1]
        k += 1

    depth = [0] * (n + 1)
    for i in range(2, n + 1):
        depth[i] = depth[bosses[i - 2]] + 1

    out = []
    app = out.append
    for _ in range(q):
        a = next(it)
        b = next(it)

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

        j = 0
        while diff:
            if diff % 2 != 0:
                a = pre[a - 1][j]
            diff //= 2
            j += 1

        if a != b:
            for k in range(maxk, -1, -1):
                if pre[a - 1][k] != pre[b - 1][k]:
                    a = pre[a - 1][k]
                    b = pre[b - 1][k]
            a = pre[a - 1][0]

        app(str(a))

    print("\n".join(out))


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: TIME LIMIT EXCEEDED