Изменения
Нет описания правки
=== Запрос ===
Обозначим <tex>I[u]</tex> {{---}} функция, возвращающая все индексы ячеек любой индекс ячейки в списке глубин <tex>depth[start..end]</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>
Приведенный выше алгоритм работает верно.
|proof=
Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Для определенности считаем, что <tex>u</tex> является первой при поиске в глубину. Обозначим <tex>a</tex> {{---}} любой индекс из На отрезке <tex>depth[I[u]</tex>, <tex>b</tex> {{---}} из <tex>I[v]</tex>. На отрезке <tex>depth[a..end]</tex> (<tex>end</tex> {{---}} последний элемент в <tex>depth</tex>) хранятся узлы посещенные после <tex>u</tex> и, быть может, некоторые вершины из поддерева с корнем <tex>u</tex>(которые имеют глубину больше глубины <tex>u</tex>). Аналогично на <tex>depth[1..bI[v]]</tex> {{---}} вершины, посещенные до <tex>v</tex> и некоторые вершины из поддерева <tex>v</tex>. Рассмотрим теперь отрезок <tex>depth[aI[u]..bI[v]]</tex>. Поскольку этот отрезок {{---}} путь из <tex>u</tex> в <tex>v</tex>, он проходит через их наименьшего общего предка <tex>w</tex>(в дереве есть только один простой путь между вершинами). Покажем, что его глубина минимальна на отрезке <tex>depth[aI[u]..bI[v]]</tex>. Допустим обратное. Все потомки <tex>w</tex> имеют глубину больше. Но тогда получим, что поиск в глубину вышел из поддерева вершины <tex>w</tex> раньше, чем посетил вершину <tex>v</tex>.
}}
