Link-Cut Tree
Динамические деревья (англ.dynamic tree) используются в двух областях: потоки и динамические графы. В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока. В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Нужно быстро обрабатывать изменения, а также уметь проверять связность, искать диаметр. Динамические деревья являются инструментом, который позволяет легко решать эти задачи. Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов link и cut.
Link-cut tree — это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:
- [math]\mathrm[/math] — искать минимум на пути от вершины до корня,
- [math]\mathrm
- [math]\mathrm
- [math]\mathrm[/math] — отрезать дерево с корнем в вершине [math]\mathrm[/math] .
Среднее время выполнения каждой операции — [math]O(\log n)[/math] . Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году.
Решение задачи в частном случае
Сначала рассмотрим частный случай, в котором все деревья — это пути, и мы хотим уметь:
- [math]\mathrm
- [math]\mathrm[/math] — разбить один путь на два,
- [math]\mathrm
Если бы не последние две операции, то можно было бы применить дерево отрезков, сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Эту задачу можно решить при помощи декартового дерева по неявному ключу. Также, если использовать какие-нибудь сливаемые деревья, то [math]\mathrm[/math] и [math] \mathrm[/math] реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах. В качестве сливаемых деревьев выберем splay-деревья, в которых ключи выбираются равными глубине вершины.
Тогда операции [math]\mathrm[/math] будет соответствовать [math]\mathrm[/math] .
[math]\mathrm
Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить величину [math]\Delta w[/math] , которая равна разнице между весом вершины и весом её родителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:
[math]w(u) = \displaystyle \sum_v^<> \Delta w(v)[/math] , где [math] v [/math] — все предки вершины [math] u [/math] .
При прибавлении [math]\alpha[/math] на пути от вершины [math]v[/math] до корня, сначала вызывается [math]\mathrm[/math] , после чего в левом поддереве находятся вершины, которые лежат на пути к корню. Затем надо прибавить [math]\alpha[/math] к [math]\Delta w(v)[/math] и, чтобы сохранить веса вершин, которые находятся ниже в пути, вычесть [math]\alpha[/math] от [math]\Delta w(right(v))[/math] .
Для реализации [math]\min[/math] будем хранить минимум уже для всего поддерева. Чтобы искать минимум от вершины [math]v[/math] , надо вызвать [math]\mathrm[/math] и сравнить её вес с минимумом левого поддерева, в котором теперь находятся все вершины пути кроме [math]v[/math] . Определим [math]\Delta \min (v)[/math] таким образом, чтобы сохранялся следующий инвариант: [math]\min (v) = \Delta \min (v) + w(v) [/math] . Пусть [math]l[/math] и [math]r[/math] дети [math]v[/math] , тогда
Link-cut tree
Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо сплошным, либо пунктирным. Все пути в link-cut дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель [math]pathparent[/math] .
expose(u)
Ключевая операция в link-cut-деревьях — [math]\mathrm[/math] . После её выполнения [math]u[/math] лежит на одном пути с корнем link-cut дерева и при этом становится корнем в splay-дереве получившегося пути. Для этого она поднимается вверх по link-cut дереву, и если какой-нибудь путь пересекает путь от [math]u[/math] до корня, то она его отрезает, разъединяя splay-дерево и делая соответствующее сплошное ребро пунктирным ребром.
function expose(u: tree): splay(u) v u while v root p pathparent(v) //получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня splay(p) //теперь в правом поддереве p находятся вершины пути, которые находятся ниже чем p в link-cut-дереве, parent(right(p)) null //поэтому правое поддерево p делаем новым путем pathparent(right(p)) p right(p) v //объединяем оставшийся и построенный пути w(v) -= w(p) min(p) min[math]\vartriangle[/math]min(left(p)) + w(left(p)), min(right(p)) + w(right(p))> pathparent(v) null v p splay(u)
add(v, c)
Чтобы прибавить константу на пути от [math]v[/math] до корня link-cut-дерева вызовем [math]\mathrm[/math] , что построит запрашиваемый путь в виде splay-дерева, в котором [math]v[/math] — корень, и в левом поддереве находятся вершины, которые находятся выше чем [math]v[/math] в link-cut-дереве (то есть все вершины пути без [math]v[/math] ), а в правом — те, что ниже. Тогда прибавим [math]c[/math] к [math]\Delta w(v)[/math] и вычтем константу от правого ребенка [math]v[/math] , чтобы скомпенсировать разницу и сохранить инвариант.
function add(v: tree, c: int): expose(v) w(v) += c w(right(v)) -= c
min(v)
Построим splay-дерево для пути и сравним вес корня [math]v[/math] c минимумом в левом поддереве:
function min(v: tree): int expose(v) if min(left(v)) + w(left(v)) < w(v) return min(left(v)) + w(left(v)) else return w(v)
link(v, u)
Если [math]v[/math] — корень, а [math]u[/math] — вершина в другом дереве, то [math]\mathrm
function link(v: tree, u: tree): tree expose(v) //теперь v — корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в link-cut дереве) expose(u) w(u) -= w(v) //чтобы сделать u родителем v в link-cut дереве 1. делаем путь, содержащий u, левым ребенком v в splay-дереве parent(u) v // 2. обновляем w, min left(v) u min(v) min[math]\vartriangle[/math]min(u) + w(u), min(right(v)) + w((right(v)))> return v
cut(v)
Отрезает дерево с корнем [math]v[/math] . После вызова [math]\mathrm[/math] вершина [math]v[/math] станет корнем splay-дерева, и в правом поддереве будут содержаться все вершины, которые были ниже [math]v[/math] в link-cut дереве, а в левом — те что выше. Обнулив указатель на левого ребенка [math]v[/math] и на родителя в левом поддереве, получим требуемое.
function cut(v: tree): expose(v) w(left(v)) += w(v) min(v) min[math]\vartriangle[/math]min(right(v)) + w(right(v))> parent(left(v)) null left(v) null
Оценка времени работы
Назовем ребро из [math]u[/math] в её родителя [math]v[/math] тяжелым, если количество детей [math]u[/math] равное [math]d(u) \gt \dfrac d(v)[/math] .
Операция [math]\mathrm[/math] осуществляется с помощью последовательности преобразований пунктирного ребра в сплошное ребро и другого сплошного ребра в пунктирное ребро. Обозначим количество таких преобразований за [math]M[/math] . Найдем количество преобразований сделанных в течение [math]\mathrm[/math] . Пусть [math]H[/math] — множество всех тяжелых ребер, [math]L[/math] — все легкие ребра, [math]S \rightarrow D[/math] — множество сплошных ребер, преобразованных в пунктирные в течение одного [math]\mathrm[/math] , [math]D \rightarrow S[/math] — множество пунктирных ребер, преобразованных в сплошные.
По лемме, количество легких пунктирных ребер, преобразованных в сплошные, будет не больше, чем [math]\log n[/math] .
Обозначим за [math]F[/math] лес деревьев, в которых каждое ребро либо сплошное, либо пунктирное, a [math]F'[/math] — лес, получившийся из [math]F[/math] после одного вызова [math]\mathrm[/math] . Определим потенциал [math]\Phi _(F) = n — 1 — |\|[/math] , [math]\Delta \Phi _[/math] — увеличение [math]\Phi _[/math] после одной операции [math]\mathrm[/math] .
Пусть [math]s(v)[/math] — количество вершин в поддеревьях [math]v[/math] ( здесь имеется в виду splay-дерево пути, который строится в ходе выполнения [math]\mathrm[/math] ), [math]r(v) = \log s(v)[/math] . По лемме стоимость i-той операции [math]\mathrm[/math] не превосходит [math]1 + 3 \cdot (r(t) — r(v))[/math] . Это приводит к тому, что амортизационная стоимость [math]\mathrm[/math] ограничена следующим значением:
[math]3 \cdot \log n — 3 \cdot \log (s(v)) + M[/math]
Здесь [math]M = O(\log n)[/math] , поэтому амортизационная стоимость [math]\mathrm[/math] равна [math]O(\log n)[/math] .
Применение
LCA
C помощью link-cut-дерева можно найти наименьшего общего предка:
function lca(u: tree, v: tree): tree expose(u) expose(v) return pathparent(splay(u))
Первый вызов [math]\mathrm[/math] построит путь от [math]u[/math] до корня. Второй пересечет этот путь в наименьшем общем предке, поэтому в splay-дереве, которому принадлежит [math]u[/math] , хранится указатель [math]pathparent[/math] на [math]\mathrm[/math] , после [math]\mathrm(u)[/math] он будет находиться в [math]u[/math] .
См. также
Источники информации
Источник