Сжатые деревья
Рассмотрим следующую задачу: дано дерево на $n$ вершинах, и поступают запросы. Запрос выглядит таким образом:
- Дается подмножество размера $k$ из вершин дерева.
- Надо вывести сумму попарных расстояний между вершинами в подмножестве.
На каждый запрос надо отвечать за $O(k \log k)$
Идея решения
Если бы мы решали задачу для всего дерева, то она была бы достаточно простой задачей на динамику. $dp_v$ - сумма попарных расстояний до $v$ в поддереве $v$, $size_v$ - размер поддерева $v$, $ans_v$ - сумма попарных расстояний между вершинами, lca которых равен $v$. Тогда пересчет следующий:
- $size_v = 1 + \sum_{v \rightarrow u} size_{u}$
- $dp_v = \sum_{v \rightarrow u} size_u + dp_u$
- $ans_v = dp_v + \sum_{v \rightarrow u} dp_u \cdot (sz_v - 1 - sz_u)$
Разумеется, таким методом задача не решится, но он поможет нам в дальнейшем.
Идея решения
Построим сжатое дерево на подмножестве вершин. Оно будет содержать в себе все вершины подмножества и попарные $lca$ всех вершин подмножества. На таком дереве можно посчитать динамику, аналогичную предыдущей, и ответить на вопрос задачи. Осталось за $O(k \log k)$ построить сжатое дерево.
На самом деле, это достаточно просто - нужно отсортировать вершины в порядке $tin$ (см. эйлеров обход дерева), а потом добавить в множество $lca$ всех соседей в порядке сортировки. Строить дерево явно не обязательно, но можно сначала сохранить ссылки на предка, делая второй проход в порядке сортировки со стеком, и храня в стеке помеченные вершины на пути до корня, обрабатывая $tin, tout$.
Понятно, что для всех пар вершин их $lca$ будет принадлежать сжатому дереву. Приведем доказательство от противного. Пусть $lca(v, u) = A$ не принадлежало. Тогда рассмотрим отрезок отсортированных вершин от $v$ до $u$. Если вспомнить, что $lca$ можно искать с помощью RMQ. Тогда тк $lca(v, u)$ принадлежал этому отрезку, то находя $lca$ последовательно для всех помеченных вершин от $v$ до $u$, мы в какой-то момент обязательно наткнемся на $A$, который будет минимумом на отрезке.
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s