Общий предок рода


Отправить решение Решать в редакторе

Сложность: 50%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Общий предок рода

Дано родословное дерево: у каждого, кроме родоначальника (номер 1), есть отец, причём номер отца меньше номера сына. Для q запросов найдите наименьшего общего предка двух людей (предком считается и сам человек).

Формат ввода

В первой строке n и q (1 ≤ n, q ≤ 10⁵). Во второй — p₂, …, pₙ (1 ≤ pᵢ < i). Далее q строк с uⱼ, vⱼ.

Формат вывода

Для каждого запроса — номер общего предка, по одному в строке.

Пример 1

Вход:

5 2
1 1 2 2
4 5
4 3

Выход:

2
1

Комментарии

Еще нет ни одного комментария.