Задача №111711. Dynamic LCA

Постановка задачи о {Наименьшем общем предке} такова: дано дерево T с выделенным корнем и две вершины u и v, lca(u, v) - вершина с максимальной глубиной, которая является предком и u, и v. Например, в картинке внизу lca(8, 7) - вершина 3.

С помощью операции chroot(u) мы можем менять корень дерева, достаточно отметить u, как новый корень, и направить ребра вдоль пути от корня. Наименьшие общие предки вершин поменяются соответствующе. Например, если мы сделаем chroot(6) на картинке сверху, lca(8, 7) станет вершина 6. Получившееся дерево изображено снизу.

Вам дано дерево T. Изначально корень этого дерева - вершина 1. Напишите программу, которая поддерживает эти две операции: lca(u, v) и chroot(u).

Входные данные

Входной файл состоит из нескольких тестов.

Первая строка каждого теста содержит натуральное число n  — количество вершин в дереве (1 ≤ n ≤ 100 000). Следующие n - 1 строки содержат по 2 натуральных числа и описывают ребра дерева. Далее идет строка с единственным натуральным числом m — число операций —. Следующие m строк содержат операции. Строка "? u v" означает операцию lca(u, v), a строка "! u" - chroot(u). Последняя строка содержит число 0.

Сумма n для всех тестов не превосходит 100 000. Сумма m для всех тестов не превосходит 200 000.

Выходные данные

Для каждой операции "? u v" выведите значение lca(u, v). Числа разделяйте переводами строк.

Система оценки:

Система тестов состоит из двух групп:

Первая группа состоит из тестов, для которых выполняется ограничение \(n \le 100\), \(m \le 10000\). За прохождение всех тестов группы ставится 55 баллов.

Вторая группа стоит из тестов, в которых нет дополнительных ограничений. За прохождение тестов этой группы и всех предыдущих тестов ставится дополнительно 45 баллов.

Примеры
Входные данные
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
10
? 4 5
? 5 6
? 8 7
! 6
? 8 7
? 4 5
? 4 7
? 5 9
! 2
? 4 3
0
Выходные данные
2
1
3
6
2
3
6
2
Сдать: для сдачи задач необходимо войти в систему