Предлагаю следующий вариант: хранить времена tin, tout в декартовом дереве. В этом случае подвешивание нового поддерева — это добавление нового отрезка внутрь этого декартового дерева, а заодно следующие две операции: 1) к временам входа-выхода самого поддерева прибавить значение tin входа в их "отца" 2) к временам входа-выхода основного дерева, больших чем tin вершины, за которую подвесили, прибавить размер поддерева(то есть, ко всему суффиксу, начиная от подвешиваемой вершины, добавить значение 2 * n₁, где n₁ — размер поддерева). Вариант, конечно, не самый изящный, но пока придумать ничего элегантнее не могу.

Сначала прочитал невнимательно и увидел переподвешивать дерево.

Здесь нужно знать алгоритм нахождения lca без tin и tout. Это не так сложно, сперва надо уравнять две вершины u и v по высоте. Далее надо найти первую вершину которая совпадает при подъеме из u и v на высоту h. Это работа для двоичных подъемов.

В нашем массиве pr мы храним предка на каком то уровне, либо -1 если такого предка пока нет. Когда происходит подвешивание надо пару -1 заменить на что-то другое. Ок, запомним это.

Когда происходит подвешивание надо сделать pr[0][u] = v. Обозначить непосредственого предка вершины u.

Когда происходит поиск lca нужно уметь делать две вещи:

1) Понимать "настоящая" или нет -1. Это делается рекурсивным алгоритмом.

2) Находить расстояние до корня. (Если умеем делать первый пункт, то умеем и этот).

Сложность получается log ^ 2 на запрос lca.