Изменения

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