Изменения
→Алгоритм
2) Запустим обход в глубину из корня, который будет строить список посещений узлов. Глубина текущей вершины добавляется в список при входе в эту вершину, а также после каждого возвращения из её сына.
=== Запрос ===
Пусть имеется запрос пара узлов <tex>u, v.</tex> Обозначим <tex>I[u]</tex> - индекс ячейки в списке глубин, в которой хранится глубина узла <tex>u.</tex> Тогда запрос минимального элемента В результате получился список глубин вершин, в котором наименьшему общему предку вершин <tex>u, v</tex> соответствует минимальная глубина на отрезке <tex>[I[u], I[v]]</tex> будет равен глубине наименьшего общего предка узлов <tex>u, v.</tex>
== Доказательство корректности алгоритма ==
