Изменения

Случай, когда <tex> u </tex> является наименьшим общим предком вершин <tex> u </tex> и <tex> v </tex> отработает , обработается правильно, потому что по алгоритму в этот момент <tex> ancestor[\mathrm{find}(u)] = u </tex>.

ПредположимПусть теперь наименьшим общим предком вершин <tex> u </tex> и <tex> v </tex> будет вершина, что нашли отличная от этих двух. Во время обработки запроса алгоритм точно вернёт общего предкаэтих двух вершин, который не является наименьшимтак как он будет предком одной из вершин по массиву <tex> ancestor </tex>, тогда это нас моментально приводит к противоречиюа предком другой из-за обхода в глубину.  Покажем, потому что запросмы должны были рассмотреть ранее {{---}} на минимальном предкенайдём наименьшего предка. Если он Пусть это не минимальный, значит, есть на какойтак. Тогда существует какая-то большей глубине, то есть такая вершина<tex> w </tex>, которая была посещена раньше и для которой условия на тоже является предком вершин <tex>u</tex> и <tex>v</tex> выполнялисьи из которой мы вышли позже во время обхода в глубину. Но тогда ситуация, значитчто одна из вершин посещена, а у другой рассмотрены все дети, тогда должна была найтись эта вершина выполниться раньше, и в качестве ответа должна была вернуться вершина <tex> w </tex>. Заметим, что для корректности алгоритма достаточно было бы одного массива <tex>LCAdsu </tex>, а представителем класса всегда выбирать наименьшего общего предка вершин класса. Это несложно сделать, так как мы всегда объединяем ребёнка со своим родителем. Но в таком случае алгорим получился бы менее эффективным, потому что одна только эвристика сжатия путей работает недостаточно быстро.