10564: HLD - LCA
Відправити розв'язок
Бали:
100 (partial)
Time limit:
1.0s
Memory limit:
64M
Author:
Problem type
Allowed languages
Brain****, C, C++, Java, Pascal, Python, v8js
Реалізуйте HEavy-Light decomposition і за її допомогою відповідайте на запити знаходження найближчого спільного предка для двох вершин.
Формат вхідних даних
В першому рядку число \(N\) - кліькість вершин дерева (\(1 \le N \le 2*10^5\))
В кожному з наступних \(N-1\) рядків по два числа \(v1,v2\) які описують ребра дерева. (\(1 \le v1,v2 \le 2*10^5\))
В третьому рядку число \(M\) - кількість запитів (\(1 \le M \le 2*10^5\))
В кожному з наступних \(M\) рядків по два числа \(q1,q2\) - номера вершин для яких необхідно знайти найменшого спільного предка (\(1 \le q1,q2 \le N\))
Корінь дерева - вершина з номером 1
Формат вихідних даних
Для кожного запиту виведіть в окремому рядку відповідь - номер найменшого спільного предка
Приклад вхідних даних
5
1 2
1 3
2 4
2 5
4
3 4
5 4
5 1
2 2Приклад вихідних даних
1
2
1
2
Коментарі
"В кожному з наступних n рядків..."; Має бути n-1
так, дякую, підправимо