Изменения

Для каждого класса мы образуем множество, и представителя этого множества.

Когда мы приходим в новую вершину <tex>v</tex> мы должны добавить её в новый класс (<tex>ancestor[v] = v</tex>), а когда просмотрим всё поддерево какого-то ребёнка, мы должны объединить это поддерево с нашим классом (операция <tex>union</tex>), и не забыть установить представителя как вершину <tex>v</tex> (в зависимости от реализации это может быть какая-то другая вершина).

После того как мы обработали всех детей вершины <tex>v</tex>, мы можем ответить на все запросы вида (<tex>v</tex>,<tex>u</tex>) где <tex>u</tex> {{---}} уже посещённая вершина.

Нетрудно заметить что ответ для <tex>lca(v, u) = ancestor[find(u)]</tex>.Так же можно понять что для каждого запроса это условие (что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.