Heavy-light decomposition

Техника $HLD$ позволяет декомпозировать дерево на пути таким образом, что любой путь на дереве распадается на $O(\log n)$ путей из декомпозиции.

Идея

Назовем ребро тяжелым, если оно ведет в сына с максимальным размером (при равенстве размеров назовем тяжелым любое из возможных). У вершины не должно быть больше одного тяжелого ребра. Оставшиеся ребра назовем легкими.

Теперь рассмотрим путь от вершины $v$ до корня. На нем может быть $O(\log n)$ легких вершин, потому что если ребро $v \rightarrow parent_v$ легкое, то $size_{parent_v} \ge 2 \cdot size_v$. Таким образом, если бы ребер на пути до корня будет больше логарифма, то размер всего дерева не будет равен $n$.

Тогда разобьем дерево на пути, состоящие из тяжелых ребер. Любой запрос на пути разбивается на $\log$ запросов на вертикальных тяжелых путях. На этих путях построим какую-нибудь структуру данных, которая поможет нам отвечать на такие запросы (чаще всего это будет дерево отрезков).

Реализация

В реальности никто не пишет много разных деревьев отрезков, а все пути скидываются в одно дерево. Как? Переупорядочим списки детей у каждой вершины, поставив тяжелое ребро первым. Тогда если сделать эйлеров обход дерева, выписав вершины в порядке их $tin$-а, то пути из декомпозиции будут образовывать подотрезки этого пути. Соответственно, можно построить всего одно дерево отрезков.

Примечание. В такой реализации есть дополнительная возможность применять операции к поддереву.

 1 void dfs(int v, int p) {
 2 	sz[v] = 1;
 3 	int id = 0;
 4 	for (int i = 0; i < g[v].size(); i++) {
 5 		int to = g[v][i];
 6 		dfs(to, v);
 7 		sz[v] += sz[to];
 8 		if (sz[to] > sz[g[v][id]]) {
 9 			id = i;
10 		}
11 	}
12 	swap(g[v][id], g[v][0]);
13 }
14 
15 /*
16 строим hld
17 up[v] -> первая вершина на 
18          вертикальном пути из тяжелых ребер, 
19          в котором лежит v
20 pos[i] хранит эйлеров обход дерева (только первое вхождение
21 */
22 
23 void build(int v, int p) {
24 	if (up[v] == -1) {
25 		up[v] = up[p];
26 	}
27 	pos[timer] = v;
28 	tin[v] = timer++;
29 	bool f = 0;
30 	for (auto to : g[v]) {
31 		if (f) {
32 			up[to] = to;
33 		}
34 		build(to, v);
35 		f = 1;
36 	}
37 	tout[v] = tin[v] + sz[v] - 1;
38 }
39 
40 int lca(int v, int u);
41 bool parent(int v, int u);
42 
43 void query_vert(int v, int u) {
44     while (up[v] != up[u]) {
45         get(up[v], v);
46         v = parent[up[v]];
47     }
48     get(u, v);
49 }
50 
51 void query(int v, int u) {
52      query_vert(v, lca(v, u));
53      query_vert(u, lca(v, u)); // аккуратно - вот тут можно дважды обработать lca. 
54 }

---

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s