Heavy-light декомпозиция — это мощный метод решения задач на запросы на путях, когда также есть запросы обновлений. Если запросов обновления нет, то лучше написать что-нибудь попроще.
Heavy-light декомпозицией корневого дерева называется результат следующего процесса: каждой вершины $v$ посмотрим на всех её непосредственных детей $u$, выберем среди них ребёнка $u_{max}$ с самым большим размером поддерева — если таких больше одного, то любого из них — и назовём ребро $(v, u_{max})$ тяжелым (англ. heavy), а все остальные рёбра — лёгкими (англ. light).
Таким образом, дерево распалось на тяжелые и лёгкие рёбра. Это разбиение и называют heavy-light декомпозицией.
Докажем несколько полезных свойств такого разбиения.
Утверждение. Дерево разбивается на непересекающиеся пути из тяжелых рёбер.
Доказательство. В каждую вершину входит не более одного тяжелого ребра, и из каждой вершины исходит не более одного тяжелого ребра.
Назовём блоком либо лёгкое ребро, либо вертикальный путь из тяжелых рёбер.
Утверждение. На любом вертикальном пути будет не более $O(\log n)$ блоков.
Доказательство разбивается на две части:
- Лёгких ребер на вертикальном пути будет не более $O(\log n)$: рассмотрим самую нижнюю вершину и будем идти по вертикальному пути снизу вверх. Каждый раз, когда мы переходим по лёгкому ребру, размер поддерева текущей вершины увеличивается в два раза, потому что если вершина связана с родителем лёгким ребром, то у него есть какой-то другой ребёнок, который не легче текущего.
- Непрерывных путей из тяжелых рёбер будет не более $O(\log n$: если это не конец или начало пути, то каждый такой путь окружают два лёгких ребра, а их всего $O(\log n)$.
Следствие. На любом пути будет не более $O(\log n)$ блоков.
Ради этого мы всё и делали: теперь построим какую-нибудь структуру на каждом тяжелого пути (например, дерево отрезков), а при ответе на запрос (скажем, суммы на пути) разобьем его на $O(\log n)$ запросов либо к подотрезкам тяжелых путей, либо к лёгким рёбрам.
#Реализация
Большинство публичных реализаций HLD — это 120-150 строк кода. Мы же воспользуемся следующим трюком, который сильно упростит нам жизнь: перенумеруем вершины дерева так, что для каждого тяжелого пути все его вершины будут иметь последовательные номера.
А именно, на этапе подсчёта размера поддеревьев, изменим список смежности каждой вершины так, чтобы в самом начале шел её «тяжелый» ребёнок. Тогда, если запустить обычный эйлеров обход графа, то массив tin будет нужной нумерацией, потому что в каждой вершине мы шли в своего тяжелого ребёнка в первую очередь.
vector<int> g[maxn];
int s[maxn], p[maxn], tin[maxn], tout[maxn];
int head[maxn]; // «голова» тяжелого пути, которому принадлежит v
int t = 0;
void sizes(int v = 0) {
s[v] = 1;
for (int &u : g[v]) {
sizes(u);
s[v] += s[u];
if (s[u] > s[g[v][0]])
// &u -- это ссылка, так что её легально использовать при swap-е
swap(u, g[v][0]);
}
}
void hld(int v = 0) {
tin[v] = t++;
for (int u : g[v]) {
// если это тяжелый ребенок -- его next нужно передать
// в противном случае он сам является головой нового пути
head[u] = (u == g[v][0] ? head[v] : u);
hld(u);
}
tout[v] = t;
}
Теперь мы можем построить дерево отрезков или какую-нибудь другую структуру поверх массива размера $n$ и при запросе к какому-нибудь тяжелому пути делать запрос к отрезку в этой структуре.
#Как им решать задачи
Простейший пример задачи на HLD: дано дерево, в каждой вершине которого записано какое-то число, и поступают запросы двух типов:
- Узнать минимальное число на пути между $v_i$ и $u_i$.
- Заменить число $v_i$-той вершины на $x_i$.
Подвесим дерево за произвольную вершину и построим на нём HL-декомпозицию с деревом отрезков в качестве внутренней структуры. Его код мы приводить не будем и посчитаем, что оно реализовано примерно так же, как в соответствующей статье и имеет методы upd(k, x) и get_min(l, r).
int val[maxn];
segtree st(0, n);
При операции обновления нам нужно просто обновить нужную ячейку в дереве отрезков:
void upd(int v, int x) {
st.upd(tin[v], x);
}
Запрос минимума сложнее — нам нужно разбить исходный запрос на запросы к вертикальным путям:
int ancestor(int a, int b) {
return tin[a] <= tin[b] && tin[b] < tout[a];
}
void up(int &a, int &b, int &ans) {
while (!ancestor(head[a], b)) {
ans = min(ans, st.get_min(tin[head[a]], tin[a]));
a = p[head[a]];
}
}
int get_min(int a, int b) {
int ans = inf;
up(a, b, ans);
up(b, a, ans);
if (!ancestor(a, b))
swap(a, b);
ans = min(ans, st.get_min(tin[a], tin[b]));
return ans;
}
Заметьте, что чтобы разбить путь на два вертикальных, нам даже не нужно отдельно решать задачу LCA: поднимаясь по тяжелым путям, мы за $O(\log n)$ подъемов приходим к наибольшему общему предку.
#Замечания
- Если в задаче нет запросов обновления, то можно «кэшировать» запросы. Заметим, что большинство запросов к структуре, которые надо сделать, находятся на префиксах тяжелых путей, и на них можно отвечать за $O(1)$ предподсчетом, и префиксных подзапросов будет $O(\log n)$ на запрос. Также придется сделать $O(1)$ запросов к структуре, которые будут работать за $O(\log n)$. Получаем $O(\log n)$ на запрос.
- Так как наша реализация HLD строит структуру данных на эйлеровом обходе дерева, мы можем добавить запросы к поддеревьям, ведь поддеревья — это подотрезки эйлерова обхода.