Изменения
Нет описания правки
=== Запрос ===
Обозначим <tex>I[u]</tex> {{---}} функция, возвращающая любой индекс ячейки в списке глубин <tex>depth</tex>, в котором хранится глубина узла <tex>u</tex>. Ее можно строить во время обхода в глубину.
Пусть имеется запрос пара узлов <tex>u, v.</tex> В результате обхода в глубину получился список глубин вершин, в котором наименьшему общему предку вершин <tex>u, v</tex> соответствует минимальная глубина на отрезке <tex>depth[I[u], I[v]].</tex> Можно брать любое значение <tex>I[u].</tex> Для определённости <tex>I[u] \le I[v].</tex>
=== Доказательство корректности алгоритма ===
