Link-Cut Tree

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

• искать минимум на пути от вершины до корня;
• прибавлять константу на пути от вершины до корня;
• link(u,w) -- подвешивать одно дерево на другое;
• cut(v) -- отрезать дерево с корнем в вершине v.

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

Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в которм ключи выбираются равными глубине вершины.

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

Тогда операциям link и cut будут соответсвовать merge и split.

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

сумма

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

Для поиска минимума поступим аналогично. Определим [math]\Delta min(v)[/math] таким образом, чтобы сохранялся следующий инвариант: [math]min(v) = \Delta min(v) + w(v) [/math]. Пусть [math]l[/math] и [math]r[/math] дети [math]v[/math], тогда

[math]min(v) = min\{w(v), min(l), min(r)\}[/math]

[math]\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)\}[/math]

Чтобы найти минимум на пути, надо вызвать [math]splay(v)[/math], а затем сравнить минимум [math]v[/math] и минимум её левого ребенка.

Link-cut tree

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

Ключевая операция в link-cut-деревьях — [math]expose(u)[/math]. После её выполнения [math]u[/math] лежит на одном пути с корнем представляемого дерева и при этом становится корнем в splay-дереве получившегося пути.

expose(u)
    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{0, Δ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]expose(v)[/math], что построит запрашиваемый путь в виде splay-дерева, в котором [math]v[/math] - корень, и в левом поддереве находятся вершины, которые находятся выше чем [math]v[/math] в link-cut-дереве (то есть все вершины пути без [math]v[/math]), а в правом - те, что ниже. Тогда прибавим [math]c[/math] к [math]\Delta w(v)[/math] и вычтем константу от правого ребенка [math]v[/math], чтобы скомпенсировать разницу и сохранить инвариант.

add(v, c)
    expose(v)
    Δw(v) += c
    Δw(right(v)) -= c

min(v)

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

min(v)
    expose(v)
    if (Δmin(left(v)) + Δw(left(v)) < Δw(v))
    then
        return Δmin(left(v)) + Δw(left(v))
    else
        return Δw(v)

link(v, u)

Если [math]v[/math] - корень, а [math]u[/math] - вершина в другом дереве, то [math]link(v, u)[/math] соединяет два дерева добавлением ребра [math](v, u)[/math], причем [math]u[/math] становится родителем [math]v[/math].

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

cut(v)

Отрезает дерево с корнем [math]v[/math]. После вызова [math]expose(v)[/math] [math]v[/math] станет корнем splay-дерева, и в правом поддереве будут содержатся все вершины, которые были ниже [math]v[/math] в представляемом дереве, а в левом - те что выше. Обнулив указатель на левого ребенка [math]v[/math] и на родителя в левом поддереве, получим требуемое.

cut(v)
    expose(v)
    Δw(left(v)) += Δw(v)
    Δmin(v) = min{0, Δmin(right(v)) + Δw(right(v))}
    left(v) = null
    parent(left(v)) = null