Можно забить на добавление вершин. Поскольку в задаче нет команд "удалить вершину" и гаранитируется, что в каждый момент времени структура будет деревом, то можно просто сначала создать дерево из всех вершин, и потом в нем выполнить все LCA.
Воспользуйтесь алгоритмом тарьяна:
https://e-maxx.ru/algo/lca_linear_offline для получения ответов на все запросы LCA сразу.
Сначала при вводе создайте дерево целиком и запомните все запросы Get в массив. Потом пройдитесь по массиву запросов и раскидайте их в списки на вершинах, как надо в алгоритме таръяна.
Вам надо лишь чуть-чуть подкорректировать этот код, чтобы вместе с вершиной-запросом добавлять в списки к вершинам номер этого запроса. И тогда вместо вывода
v+1, q[v][i]+1
вы сможете записать ответ в массив по нужному индексу.
Ну или воспользуйтесь
онлайн алгоритмом для поиска LCA через обход со временем входа/выхода и деревом отрезков на минимимум.