Задачи
LCA offline (Easy)
LCA offline (Easy)
Изначально имеется дерево, состоящее только из корня (вершина с номером 1). Требуется научиться отвечать на следующие запросы:
ADD~a~b — подвесить вершину b за вершину a (гарантируется, что вершина a уже существует).
GET~a~b — вернуть LCA вершин a и b.
Вершины имеют номера от 1 до n. В каждый момент времени у нас имеется одно дерево.
Входные данные
В первой строке содержится количество запросов k. Следующие k строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит 1000.
Выходные данные
Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.
Пример
Входные данные #1
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 1 2 5