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