Company Queries II

import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate, groupby
from functools import lru_cache, cmp_to_key, reduce
from math import gcd, isqrt, comb, inf, pi, sqrt, atan2, hypot


def main():
    data = sys.stdin.buffer.read().split(); idx = 0
    # n = int(data[idx]); idx += 1
    n, q = map(int, data[idx:idx + 2]); idx += 2
    a = list(map(int, data[idx:idx + n-1])); idx += (n-1)

    out = []

    par = [0, 0] + a

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

    size = [1] * (n + 1)
    for i in range(n, 1, -1):
        size[par[i]] += size[i]

    heavy = [0] * (n + 1)
    for i in range(2, n + 1):
        p = par[i]
        if heavy[p] == 0 or size[i] > size[heavy[p]]:
            heavy[p] = i

    head = [0] * (n + 1)
    head[1] = 1
    for i in range(2, n + 1):
        if heavy[par[i]] == i:
            head[i] = head[par[i]]
        else:
            head[i] = i

    out = []

    for _ in range(q):
        a, b = map(int, data[idx:idx + 2]); idx += 2
        while head[a] != head[b]:
            if depth[head[a]] > depth[head[b]]:
                a = par[head[a]]
            else:
                b = par[head[b]]
        out.append(a if depth[a] < depth[b] else b)

    





    sys.stdout.write("\n".join(map(str, out)) + "\n")  # one value per line


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