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