Когда мы приходим в новую вершину <tex>v</tex> мы должны добавить её в новый класс (<tex>ancestor[v] = v</tex>), а когда просмотрим всё поддерево какого-то ребёнка, мы должны объединить это поддерево с нашим классом (операция <tex>union</tex>), и не забыть установить представителя как вершину <tex>v</tex> (в зависимости от реализации это может быть какая-то другая вершина).
Зафиксируем вершину <tex>v</tex>Предположим, и выделим путь от корня до этой вершины. Теперь все рёбра "левее" этого пути уже добавлены в <tex>dsu</tex>что нашли предка, все рёбра правее — ещё который не обработаныявляется наименьшим, а все рёбра на пути — обработаны, но в <tex>dsu</tex> ещё не добавлены, так как в <tex>dsu</tex> мы добавляем при выходе.Тогда можно заметитьтогда это нас моментально приводит к противоречию, потому что любая вершина из обработанных в <tex>dsu</tex> цепляются к какойзапросмы должны были рассмотреть ранее {{---то вершине текущего пути, в <tex>dfs</tex>.К самой первой вершине этого пути, до которой мы доберёмся, если будем просто подниматься. Очевидно, это и есть <tex>lca</tex>}} на минимальном предке.
После того как мы обработали всех детей вершины <tex>v</tex>, мы можем ответить на все запросы вида (<tex>v</tex>,<tex>u</tex>) где <tex>u</tex> {{---}} уже посещённая вершина.
