3622
правки
Изменения
→Корректность
== Корректность ==
Случай, когда <tex> u </tex> является наименьшим общим предком вершин <tex> u </tex> и <tex> v </tex>, обработается правильно, потому что по алгоритму в этот момент <tex> ancestorlcaClass[\mathrm{find}(u)] = u </tex>.
Пусть теперь наименьшим общим предком вершин <tex> u </tex> и <tex> v </tex> будет вершина, отличная от этих двух. Во время обработки запроса алгоритм точно вернёт общего предка этих двух вершин, так как он будет предком одной из вершин по массиву <tex> ancestor lcaClass </tex>, а предком другой из-за обхода в глубину.
Покажем, что найдём наименьшего предка. Пусть это не так. Тогда существует какая-то вершина <tex> w </tex>, которая тоже является предком вершин <tex> u </tex> и <tex> v </tex>, и из которой мы вышли раньше во время обхода в глубину. Но тогда ситуация, что одна из вершин посещена, а у другой рассмотрены все дети, должна была выполниться раньше, и в качестве ответа должна была вернуться вершина <tex> w </tex>.
