HL-декомпозиция — это мощный метод решения задач на запросы на путях, когда также есть запросы обновлений. Если запросов обновления нет, то лучше написать что-нибудь попроще.
Heavy-light декомпозицией корневого дерева называется результат следующего процесса: каждой вершины \(v\) посмотрим на всех её непосредственных детей \(u\), выберем среди них ребёнка \(u_{max}\) (с самым большим размером поддерева) и назовём ребро \((v, u)\) тяжелым (heavy), а все остальные рёбра — лёгкими (light). При этом, если самых «тяжелых» детей будет больше одного, то выберем любого.
Таким образом, дерево распалось на тяжелые и лёгкие рёбра. Докажем несколько полезных свойств такого разбиения.
Утверждение. Дерево разбивается на непересекающиеся пути из тяжелых рёбер.
Доказательство. В каждую вершину входит не более одного тяжелого ребра, и из каждой вершины исходит не более одного тяжелого ребра.
Назовём блоком либо лёгкое ребро, либо вертикальный путь из тяжелых рёбер.
Утверждение. На любом вертикальном пути будет не более \(O(\log n)\) блоков.
Доказательство разбивается на две части:
Следствие. На любом пути будет не более \(O(\log n)\) блоков.
Ради этого мы всё и делали: теперь построим какую-нибудь структуру на каждом тяжелого пути (например, дерево отрезков), а при ответе на запрос (скажем, суммы на пути) разобьем его на \(O(\log n)\) запросов либо к подотрезкам тяжелых путей, либо к лёгким рёбрам.
Большинство публичных реализаций HLD — это 120-150 строк кода. Мы же воспользуемся следующим трюком, который сильно упростит нам жизнь: перенумеруем вершины дерева так, что для каждого тяжелого пути все его вершины будут иметь последовательные номера.
А именно, на этапе подсчёта размера поддеревьев, изменим список смежности каждой вершины так, чтобы в самом начале шел её «тяжелый» ребёнок. Тогда, если запустить обычный эйлеров обход графа, то tin-ы и будут нужной нумерацией, потому что в каждой вершине мы шли в своего тяжелого ребёнка в первую очередь.
Теперь мы можем построить какую-нибудь структуру поверх массива размера \(n\) (дерево отрезков) и при запросе к какому-нибудь тяжелому пути делать запрос к отрезку в структуре.
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;
}Простейший пример задачи на HLD: дано дерево, каждой вершине которого приписано какое-то число, и поступают запросы двух типов:
Подвесим дерево за произвольную вершину и построим на нём 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;
}