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