Изменения
→Доказательство корректности алгоритма
== Доказательство корректности алгоритма ==
Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Пусть узел <tex>w</tex> - наименьший общий предок узлов <tex>u, v</tex>. Очевидно, что в поддереве с корнем <tex>w</tex> узел <tex>w</tex> будет иметь наименьшую глубину.
Осталось доказать, что всегда выполняется неравенство <tex>I[u] \le I[w] \le I[v]</tex>
== Сложность ==
