74
правки
Изменения
Нет описания правки
Зафиксируем момент: мы собираемся выйти из вершины <tex>v</tex> (обработали всех сыновей) и хотим узнать ответ для пары <tex>\langle v</tex>, <tex>u \rangle</tex>.
Тогда заметим, что ответ {{---}} это либо вершина <tex>vu</tex>, либо какой-то её предок. Значит, нам нужно найти предка вершины <tex>v</tex>, который является предком вершины <tex>u</tex> с наибольшей глубиной. Заметим, что при фиксированном <tex>v</tex> каждый из предков вершины <tex>v</tex> порождает некоторый класс вершин <tex>u</tex>, для которых он является ответом, в этом классе содержатся все вершины которые находятся "слева" от этого предка.
На рисунке разные цвета {{---}} разные классы, а белые вершины ещё не просмотренные в <tex>dfs</tex>.
Классы этих вершин не пересекаются, а значит мы их можем эффективно обрабатывать с помощью [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], которую будем храниться хранить в массиве <tex>dsu</tex>.
Будем поддерживать массив <tex>ancestor[v1 \dots n]</tex> {{---}} представитель множества в котором содержится вершина <tex>v</tex>.
Для каждого класса мы образуем множество, и представителя этого множества.
Когда мы приходим в новую вершину <tex>v</tex> мы должны добавить её в новый класс (<tex>ancestor[v] = v</tex>), а когда просмотрим всё поддерево какого-то ребёнка, мы должны объединить это поддерево с нашим классом (операция <tex>union</tex>), и не забыть установить представителя как вершину <tex>v</tex> (в зависимости от реализации это может быть какая-то другая вершина).
