Heavy-light decomposition: различия между версиями
KiKoS (обсуждение | вклад) м |
KiKoS (обсуждение | вклад) м |
||
Строка 28: | Строка 28: | ||
swap(g[v][id], g[v][0]); | swap(g[v][id], g[v][0]); | ||
} | } | ||
+ | |||
+ | /* | ||
+ | строим hld | ||
+ | up[v] -> первая вершина на | ||
+ | вертикальном пути из тяжелых ребер, | ||
+ | в котором лежит v | ||
+ | pos[i] хранит эйлеров обход дерева (только первое вхождение | ||
+ | */ | ||
+ | |||
void build(int v, int p) { | void build(int v, int p) { | ||
if (up[v] == -1) { | if (up[v] == -1) { | ||
Строка 49: | Строка 58: | ||
void query_vert(int v, int u) { | void query_vert(int v, int u) { | ||
− | while (up[v] != up[ | + | while (up[v] != up[u]) { |
get(up[v], v); | get(up[v], v); | ||
v = parent[up[v]]; | v = parent[up[v]]; |
Текущая версия на 15:48, 9 ноября 2020
Техника $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