Link-Cut Tree

Динамические деревья (англ.dynamic tree) используются в двух областях: потоки и динамические графы. В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока. В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Нужно быстро обрабатывать изменения, а также уметь проверять связность, искать диаметр. Динамические деревья являются инструментом, который позволяет легко решать эти задачи. Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов link и cut.

Link-cut tree — это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:

• $\mathrm{min(v)}$ — искать минимум на пути от вершины до корня,
• $\mathrm{add(v, c)}$ — прибавлять константу на пути от вершины до корня,
• $\mathrm{link(u, w)}$ — подвешивать одно дерево на другое,
• $\mathrm{cut(v)}$ — отрезать дерево с корнем в вершине $\mathrm{v}$.

Среднее время выполнения каждой операции — $O(\log n)$. Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году.

Решение задачи в частном случае

Сначала рассмотрим частный случай, в котором все деревья — это пути, и мы хотим уметь:

Пример построения дерева для пути

• $\mathrm{add(v, c)}$ и $\mathrm{min(v)}$ — прибавлять константу и искать минимум на некотором суффиксе (то есть на пути от вершины до корня),
• $\mathrm{cut(v)}$ — разбить один путь на два,
• $\mathrm{link(v, u)}$ — подвешивать голову одного пути к хвосту другого.

Если бы не последние две операции, то можно было бы применить дерево отрезков, сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Эту задачу можно решить при помощи декартового дерева по неявному ключу. Также, если использовать какие-нибудь сливаемые деревья, то $\mathrm{link}$ и $\mathrm{cut}$ реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах. В качестве сливаемых деревьев выберем splay-деревья, в которых ключи выбираются равными глубине вершины.

Тогда операции $\mathrm{cut}$ будет соответствовать $\mathrm{split}$.

$\mathrm{link(path1, path2)}$ соединяет голову первого пути с хвостом второго. Используем функцию $\mathrm{merge(path2, path1)}$, которая вызовет $\mathrm{splay}$ от хвоста второго пути и сделает первый путь правым ребенком корня $\mathrm{path2}$, то есть теперь $\mathrm{path1}$ находится ниже, чем $\mathrm{path2}$.

Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить величину $\Delta w$, которая равна разнице между весом вершины и весом её родителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:

$w(u) = \displaystyle \sum_v^{} \Delta w(v)$, где $v$ — все предки вершины $u$.

При прибавлении $\alpha$ на пути от вершины $v$ до корня, сначала вызывается $\mathrm{splay(v)}$, после чего в левом поддереве находятся вершины, которые лежат на пути к корню. Затем надо прибавить $\alpha$ к $\Delta w(v)$ и, чтобы сохранить веса вершин, которые находятся ниже в пути, вычесть $\alpha$ от $\Delta w(right(v))$.

Для реализации $\min$ будем хранить минимум уже для всего поддерева. Чтобы искать минимум от вершины $v$, надо вызвать $\mathrm{splay(v)}$ и сравнить её вес с минимумом левого поддерева, в котором теперь находятся все вершины пути кроме $v$. Определим $\Delta \min (v)$ таким образом, чтобы сохранялся следующий инвариант: $\min (v) = \Delta \min (v) + w(v)$. Пусть $l$ и $r$ дети $v$, тогда

$\min (v) = \min \{w(v), \min(l), \min(r)\}$

$\Delta \min(v) = \min(v) - w(v) \\ = \min\{w(v) - w(v), \min(l) - w(v), \min(r) - w(v)\} \\ = \min\{0, \ (\Delta \min(l) + w(l)) - w(v), \ (\Delta \min(r) + w(r)) - w(v)\} \\ = \min\{0, \ \Delta \min(l) + \Delta w(l), \ \Delta \min(r) + \Delta w(r)\}$

Link-cut tree

Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо сплошным, либо пунктирным. Все пути в link-cut дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель $pathparent$.

expose(u)

Ключевая операция в link-cut-деревьях — $\mathrm{expose(u)}$. После её выполнения $u$ лежит на одном пути с корнем link-cut дерева и при этом становится корнем в splay-дереве получившегося пути. Для этого она поднимается вверх по link-cut дереву, и если какой-нибудь путь пересекает путь от $u$ до корня, то она его отрезает, разъединяя splay-дерево и делая соответствующее сплошное ребро пунктирным ребром.

function expose(u: tree):
    splay(u)
    v $=$ u
    while v $\ne$ root
        p $=$ pathparent(v)        //получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня
        splay(p)                  //теперь в правом поддереве p находятся вершины пути, которые находятся ниже чем p в link-cut-дереве,
        parent(right(p)) $=$ null  //поэтому правое поддерево p делаем новым путем
        pathparent(right(p)) $=$ p
        right(p) $=$ v             //объединяем оставшийся и построенный пути
        $\vartriangle$w(v) -= $\vartriangle$w(p)
        $\vartriangle$min(p) $=$ min{0, $\vartriangle$min(left(p)) + $\vartriangle$w(left(p)), $\vartriangle$min(right(p)) + $\vartriangle$w(right(p))}
        pathparent(v) $=$ null
        v $=$ p
    splay(u)

add(v, c)

Чтобы прибавить константу на пути от $v$ до корня link-cut-дерева вызовем $\mathrm{expose(v)}$, что построит запрашиваемый путь в виде splay-дерева, в котором $v$ — корень, и в левом поддереве находятся вершины, которые находятся выше чем $v$ в link-cut-дереве (то есть все вершины пути без $v$), а в правом — те, что ниже. Тогда прибавим $c$ к $\Delta w(v)$ и вычтем константу от правого ребенка $v$, чтобы скомпенсировать разницу и сохранить инвариант.

function add(v: tree, c: int):
    expose(v)
    $\vartriangle$w(v) += c
    $\vartriangle$w(right(v)) -= c

min(v)

Построим splay-дерево для пути и сравним вес корня $v$ c минимумом в левом поддереве:

function min(v: tree): int
    expose(v)
    if $\vartriangle$min(left(v)) + $\vartriangle$w(left(v)) < $\vartriangle$w(v)
        return $\vartriangle$min(left(v)) + $\vartriangle$w(left(v))
    else
        return $\vartriangle$w(v)

link(v, u)

Если $v$ — корень, а $u$ — вершина в другом дереве, то $\mathrm{link(v, u)}$ соединяет два дерева добавлением ребра $(v, u)$, причем $v$ становится родителем $u$.

function link(v: tree, u: tree): tree
    expose(v)      //теперь v — корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в link-cut дереве)
    expose(u)
    $\vartriangle$w(u) -= $\vartriangle$w(v) //чтобы сделать u родителем v в link-cut дереве 1. делаем путь, содержащий u, левым ребенком v в splay-дереве
    parent(u) $=$ v //                                              2. обновляем $\vartriangle$w, $\vartriangle$min
    left(v) $=$ u
    $\vartriangle$min(v) $=$ min{0, $\vartriangle$min(u) + $\vartriangle$w(u), $\vartriangle$min(right(v)) + $\vartriangle$w((right(v)))}
    return v

cut(v)

Отрезает дерево с корнем $v$. После вызова $\mathrm{expose(v)}$ вершина $v$ станет корнем splay-дерева, и в правом поддереве будут содержаться все вершины, которые были ниже $v$ в link-cut дереве, а в левом — те что выше. Обнулив указатель на левого ребенка $v$ и на родителя в левом поддереве, получим требуемое.

function cut(v: tree):
    expose(v)
    $\vartriangle$w(left(v)) += $\vartriangle$w(v)
    $\vartriangle$min(v) $=$ min{0, $\vartriangle$min(right(v)) + $\vartriangle$w(right(v))}
    parent(left(v)) $=$ null
    left(v) $=$ null

Оценка времени работы

Назовем ребро из $u$ в её родителя $v$ тяжелым, если количество детей $u$ равное $d(u) \gt \dfrac{1}{2} d(v)$.

Лемма:

На пути от вершины до корня не больше $\log n$ легких ребер.

Доказательство:

$\triangleright$

Пусть $m$ — количество вершин в дереве с корнем в вершине, в которой мы сейчас находимся. Поднимаясь по легкому ребру, $m$ увеличивается в два раза, поэтому, пройдя больше $\log n$ легких ребер, получим $m \gt n$. Значит, в дереве не больше $\log n$ легких ребер.

$\triangleleft$

Операция $\mathrm{expose(u)}$ осуществляется с помощью последовательности преобразований пунктирного ребра в сплошное ребро и другого сплошного ребра в пунктирное ребро. Обозначим количество таких преобразований за $M$. Найдем количество преобразований сделанных в течение $\mathrm{expose(u)}$. Пусть $H$ — множество всех тяжелых ребер, $L$ — все легкие ребра, $S \rightarrow D$ — множество сплошных ребер, преобразованных в пунктирные в течение одного $\mathrm{expose}$, $D \rightarrow S$ — множество пунктирных ребер, преобразованных в сплошные.

$M = |\{D \rightarrow S\}| = |\{L \cap D \rightarrow S\}| + |\{H \cap D \rightarrow S\}|$

По лемме, количество легких пунктирных ребер, преобразованных в сплошные, будет не больше, чем $\log n$.

Обозначим за $F$ лес деревьев, в которых каждое ребро либо сплошное, либо пунктирное, a $F'$ — лес, получившийся из $F$ после одного вызова $\mathrm{expose}$. Определим потенциал $\Phi _{a}(F) = n - 1 - |\{H \cap solid-edges\}|$, $\Delta \Phi _{a}$ — увеличение $\Phi _{a}$ после одной операции $\mathrm{expose}$.

Лемма:

$V = M + \Delta \Phi _{a} \leqslant 1 + 2\log n$

Доказательство:

$\triangleright$

$V = M + \Delta \Phi _{a}\\ = M + |H \cap S \rightarrow D| - |H \cap D \rightarrow S| \\ \leqslant M + |L \cap D \rightarrow S| - |H \cap D \rightarrow S| \\ = 2 \cdot |L \cap D \rightarrow S| \\ =2 \cdot \log n$

$\triangleleft$

Теперь проанализируем $M$. Используя тот факт, что начальное значение $\Phi _{a}$ не превосходит $n - 1$, приходим к тому, что для деревьев с $n$ вершинами, по крайней мере за $n - 1$ операцию $\mathrm{expose}$, среднее $M$ на одну операцию будет не больше, чем $1 + 2\log n$.

Докажем, что амортизационная стоимость операции $\mathrm{expose}$ равна $O(\log n)$.

Пусть $s(v)$ — количество вершин в поддеревьях $v$ ( здесь имеется в виду splay-дерево пути, который строится в ходе выполнения $\mathrm{expose}$), $r(v) = \log s(v)$. По лемме стоимость i-той операции $\mathrm{splay}$ не превосходит $1 + 3 \cdot (r(t) - r(v))$. Это приводит к тому, что амортизационная стоимость $\mathrm{expose}$ ограничена следующим значением:

$3 \cdot \log n - 3 \cdot \log (s(v)) + M$

Здесь $M = O(\log n)$, поэтому амортизационная стоимость $\mathrm{expose}$ равна $O(\log n)$.

Применение

LCA

C помощью link-cut-дерева можно найти наименьшего общего предка:

function lca(u: tree, v: tree): tree
    expose(u)
    expose(v)
    return pathparent(splay(u))

Первый вызов $\mathrm{expose}$ построит путь от $u$ до корня. Второй пересечет этот путь в наименьшем общем предке, поэтому в splay-дереве, которому принадлежит $u$, хранится указатель $pathparent$ на $\mathrm{lca}$, после $\mathrm{splay}(u)$ он будет находиться в $u$.

См. также

• Метод двоичного подъема
• Алгоритм Тарьяна поиска LCA за O(1) в оффлайн
• Алгоритм Шибера-Вишкина

Источники информации

• А.С. Станкевич, "Дополнительные главы алгоритмов"
• Реализация LCA на link-cut дереве
• D. Sleator and R. Tarjan, "A Data Structure for Dynamic Trees"
• Jeff Erickson. Lecture 7. Link-Cut Trees
• Optimization Algorithms for Planar Graphs. Splay trees and link-cut trees
• Wikipedia — Link/cut tree