Общий предок рода
Отправить решение
Решать в редакторе
Сложность:
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
Комментарии