Изменения

2) Запустим [[Обход в глубину, цвета вершин|обход в глубину ]] из корня, который будет строить список посещений узлов. Глубина текущей вершины добавляется в список при входе в эту вершину, а также после каждого возвращения из её сына.

Обозначим <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>

Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Пусть узел Для определенности считаем, что <tex>wu</tex> является первой при поиске в глубину. Обозначим <tex>a</tex> {{---}} наименьший общий предок узлов любой индекс из <tex>I[u, v.]</tex> Очевидно, что в поддереве с корнем <tex>wb</tex> узел {{---}} из <tex>wI[v]</tex> будет иметь наименьшую глубину.Осталось доказать, что для любых значений На отрезке <tex>Idepth[ua..end],\; I[v]\; \exists</tex> значение хранятся узлы посещенные после <tex>I[w]u</tex>и, что выполняется неравенство быть может, некоторые вершины из поддерева с корнем <tex>I[u] \le I[w] \le I[v]\;(*).</tex>Пусть вершина (которые имеют глубину больше глубины <tex>u</tex> посещается раньше, чем вершина ). Аналогично на <tex>vdepth[start..b]</tex> Тогда{{---}} вершины, если вершина посещенные до <tex>v</tex> не явлется потомком и некоторые вершины из поддерева <tex>u,v</tex> будет выполняться неравенство . Рассмотрим теперь отрезок <tex>\;(*)depth[a..b]</tex> (так как после посещения поддерева, содержащего вершину . Поскольку этот отрезок {{---}} путь из <tex>u</tex>, в список будет добавлена вершина <tex>wv</tex>, а после {{---}} вершина он проходит через их наименьшего общего предка <tex>vw</tex>(в дереве есть только один простой путь между вершинами). А если вершина Покажем, что его глубина минимальна на отрезке <tex>udepth[a..b]</tex> является предком вершины . Допустим обратное. Все потомки <tex>v,w</tex> то вершина имеют глубину больше. Но тогда получим, что поиск в глубину вышел из поддерева вершины <tex>uw</tex> будет наименьшим общим предком вершин раньше, чем посетил вершину <tex>u, v</tex>. Очевидно, что неравенство выполняется. 

 Для нахождения минимального элемента на отрезке можно использовать [[Дерево отрезков. Построение|дерево отрезков]]. Длина массива глубин будет равна <tex>(2n - 1),</tex> т.е. дерево отрезков будет построено за <tex>O(n).</tex> Таким образом, препроцессинг работает за <tex>O(n).</tex> Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т.е. <tex>O(\log n).</tex>