Heavy-light декомпозиция

HL-декомпозиция — это мощный метод решения задач на запросы на путях, когда также есть запросы обновлений. Если запросов обновления нет, то лучше написать что-нибудь попроще.

Heavy-light декомпозицией корневого дерева называется результат следующего процесса: каждой вершины $v$ посмотрим на всех её непосредственных детей $u$, выберем среди них ребёнка $u_{max}$ (с самым большим размером поддерева) и назовём ребро $(v,u)$ тяжелым (heavy), а все остальные рёбра — лёгкими (light). При этом, если самых «тяжелых» детей будет больше одного, то выберем любого.

Таким образом, дерево распалось на тяжелые и лёгкие рёбра. Докажем несколько полезных свойств такого разбиения.

Утверждение. Дерево разбивается на непересекающиеся пути из тяжелых рёбер.

Доказательство. В каждую вершину входит не более одного тяжелого ребра, и из каждой вершины исходит не более одного тяжелого ребра.

Назовём блоком либо лёгкое ребро, либо вертикальный путь из тяжелых рёбер.

Утверждение. На любом вертикальном пути будет не более $O(\log n)$ блоков.

Доказательство разбивается на две части:

• Лёгких ребер на вертикальном пути будет не более $O(\log n)$: рассмотрим самую нижнюю вершину и будем идти по вертикальному пути снизу вверх. Каждый раз, когда мы переходим по лёгкому ребру, размер поддерева текущей вершины увеличивается в два раза, потому что если вершина связана с родителем лёгким ребром, то у него есть какой-то другой ребёнок, который не легче текущего.
• Непрерывных путей из тяжелых рёбер будет не более $O(\log n$: если это не конец или начало пути, то каждый такой путь окружают два лёгких ребра, а их всего $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: дано дерево, каждой вершине которого приписано какое-то число, и поступают запросы двух типов:

1. Узнать минимальное число на пути между $v_i$ и $u_i$.
2. Изменить число у $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;
}

Замечания

• Если в рамках задачи нет запросов обновления, то можно прокэшировать запросы — заметим, что большинство запросов к структуре, которые надо сделать, находятся на префиксах тяжелых путей, и на них можно отвечать за $O(1)$, и таких будет $O(\log n)$ на запрос. Также придется сделать $O(1)$ запросов к структуре, которые будут работать за $O(\log n)$. Получаем $O(\log n)$ на запрос.
• Так как наша реализация HLD строит структуру данных на эйлеровом обходе дерева, то мы можем добавить запросы к поддеревьям (ведь поддеревья — это подотрезки эйлерова обхода).