Изменения

Когда мы приходим в новую вершину <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>-уже посещённая вершина.Нетрудно заметить что ответ для <tex>lca(v,u) = ancestor(find(u))</tex>.Так же можно понять что для каждого запроса это условие(что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.

Во-первых <tex>dfs </tex> работает О (n).Во-вторых, операции по объединению множеств, которые в сумме для всех разумных <tex>n </tex> затрачивают <tex>О (n)</tex> операций. В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных <tex>n </tex> выполняется за <tex>О (1)</tex>. Итоговая асимптотика получается <tex>\mathrm{O (n + m)}</tex>, но при достаточно больших <tex>m </tex> ответ за <tex>О (1)</tex> на один запрос.