Задача №2787. LCA-Offline
Изначально имеется дерево состоящее только из корня (вершина с номером \(1\)). Требуется научиться отвечать на следующие запросы:
- ADD \(a\) \(b\) — подвесить вершину \(b\) за вершину \(a\) (гарантируется, что вершина \(a\) уже существует, а вершина \(b\) еще не существует).
- GET \(a\) \(b\) — вернуть LCA вершин \(a\) и \(b\).
Все номера вершин от \(1\) до \(N\).
В каждый момент времени у нас есть одно дерево.
Входные данные
В первой строке входного файла содержится число \(k\) — количество запросов. Следующие \(k\) строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит \(500\,000\).
Выходные данные
Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.
Примеры
Входные данные
9 ADD 1 2 ADD 1 3 ADD 2 4 GET 1 3 GET 2 3 GET 3 4 ADD 2 5 GET 4 5 GET 5 5
Выходные данные
1 1 1 2 5
Сдать: для сдачи задач необходимо войти в систему