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