53
правки
Изменения
м
Нет описания правки
=== Запрос ===
Обозначим <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>
== Доказательство корректности алгоритма ==
Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Пусть узел <tex>w</tex> {{- --}} наименьший общий предок узлов <tex>u, v.</tex> Очевидно, что в поддереве с корнем <tex>w</tex> узел <tex>w</tex> будет иметь наименьшую глубину.
Осталось доказать, что для любых значений <tex>I[u],\; I[v]\; \exists</tex> значение <tex>I[w]</tex>, что выполняется неравенство <tex>I[u] \le I[w] \le I[v]\;(*).</tex>
Пусть вершина <tex>u</tex> посещается раньше, чем вершина <tex>v.</tex> Тогда, если вершина <tex>v</tex> не явлется потомком вершины <tex>u,</tex> будет выполняться неравенство <tex>\;(*)</tex> (так как после посещения поддерева, содержащего вершину <tex>u</tex>, в список будет добавлена вершина <tex>w</tex>, а после {{- --}} вершина <tex>v</tex>). А если вершина <tex>u</tex> является предком вершины <tex>v,</tex> то вершина <tex>u</tex> будет наименьшим общим предком вершин <tex>u, v</tex>. Очевидно, что неравенство выполняется.
== Пример ==
