Изменения

Наименьшему общему предку вершин <tex>u, v</tex> соответствует минимальная глубина на отрезке <tex>depthd[I[u], I[v]]</tex>.

Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Рассмотрим отрезок <tex>depthd[I[u]..I[v]]</tex>. Поскольку этот отрезок {{---}} путь из <tex>u</tex> в <tex>v</tex>, он проходит через их наименьшего общего предка <tex>w</tex>(в дереве есть только один простой путь между вершинами), а следовательно минимум на отрезке никак не больше глубины <tex>w</tex>. ПокажемЗаметим, что его глубина минимальна в момент добавления <tex>I[u]</tex> обход посещал поддерево с корнем <tex>w</tex>. В момент добавления <tex>I[v]</tex> мы все еще в поддереве с корнем <tex>w</tex>. Значит, и на отрезке между <tex>depth[I[u]..</tex> и <tex>I[v]]</tex>. Допустим обратное. Все потомки мы находились внутри поддерева с корнем <tex>w</tex> имеют глубину больше. Но тогда получимОтсюда сделаем заключение, что поиск в глубину вышел из поддерева вершины на рассматриваемом отрезке не посещалась вершина, отличная от <tex>w</tex>, с глубиной меньшей либо равной глубины <tex>w</tex> раньше, чем посетил вершину т. к. подобной вершины нет в поддереве с корнем <tex>vw</tex>.}}.