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 void build(int v, int p) {
15 if (up[v] == -1) {
16 up[v] = up[p];
17 }
18 pos[timer] = v;
19 tin[v] = timer++;
20 bool f = 0;
21 for (auto to : g[v]) {
22 if (f) {
23 up[to] = to;
24 }
25 build(to, v);
26 f = 1;
27 }
28 tout[v] = tin[v] + sz[v] - 1;
29 }
30
31 int lca(int v, int u);
32 bool parent(int v, int u);
33
34 void query_vert(int v, int u) {
35 while (up[v] != up[i]) {
36 get(up[v], v);
37 v = parent[up[v]];
38 }
39 get(u, v);
40 }
41
42 void query(int v, int u) {
43 query_vert(v, lca(v, u));
44 query_vert(u, lca(v, u)); // аккуратно - вот тут можно дважды обработать lca.
45 }
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s