Изменения
→Псевдокод
Объявим несколько массивов, для хранения дополнительной информации:
* '''<tex>\mathtt{dist''' }</tex> {{---}} расстояние от корня до вершины.* '''<tex>\mathtt{last''' }</tex> {{---}} начало пути, на котором лежит вершина. Из всех путей выбирается путь с самой удаленной от корня дерева начальной вершины.* '''<tex>\mathtt{turn''' }</tex> {{---}} вторая вершина этого пути.
Тогда запрос на нахождение LCA:
