Изменения

* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро <tex>(u, w)</tex> (при условии, что вершины <tex>u</tex> и <tex>w</tex> принадлежат разным деревьям),

'''Дерево Для решения поставленной задачи будем представлять дерево в виде его [[Эйлеровость графов|эйлерова обхода''' графа]], а затем будем работать с [[Эйлеровость графов|эйлеровым обходом]] (англ.''Euler tour tree'') {{---}} способ представления динамического дерева, позволяющий этого графа. Это позволит выполнять указанные запросы за <tex>O(\log n)</tex>.

==Свойство эйлерова обхода== Представим дерево в виде последовательности вершин, посещеннных посещенных в порядке эйлерова обхода , начиная с корнем в вершине вершины <tex>a</tex>.

==Операцииc эйлеровыми обходами== ===Изменение корня дерева (переподвешивание)===Дано дерево с корнем в вершине <tex>a</tex>. Требуется переподвесить его к вершине <tex>h</tex>. [[Файл:Tour13.png |thumb|320px|center]] Для переподвешивания (англ. ''rerooting'') необходимо:*Разбить эйлеров обход на три части <tex>S1 </tex>, <tex>H</tex>, и <tex>S2 </tex>, где <tex>H</tex> состоит из вершин между первым и последним вхождением нового корня <tex>h</tex>.*Удалить первую вершину в <tex>S1 </tex>.*Соединить в следующем порядке: <tex>H</tex>, <tex>S2 </tex>, <tex>S1 </tex>.*Добавить <tex>\{h\}</tex> в конец последовательности. В результате получим: [[Файл:Proba.png |center]]

[[ФайлДля добавления ребра <tex>(c, g)</tex>:Link11.png |thumb|400px|center]] Для связывания деревьев *Выберем любое вхождение вершины <tex>T1 c</tex> и в эйлеров обход дерева <tex>T2T1</tex>, где .*Разрежем эйлеров обход <tex>c\in T1\ </tex>, а на две части:*: <tex>g\in T2\A1</tex> добавлением ребра {{---}} часть обхода до выбранного вхождения вершины <tex>\{c, g\} \</tex> необходимо:, включая ее.*Переподвесить дерево : <tex>T1A2</tex> к вершине {{---}} часть обхода после выбранного вхождения вершины <tex>c</tex>, включая ее.*Переподвесить дерево Аналогично, выберем любое вхождение вершины <tex>g</tex> в эйлеров обход дерева <tex>T2</tex> к вершине и разрежем его на две части <tex>B1</tex> и <tex>gB2</tex>.*Соединить получившиеся эйлеровы обходы.*Добавить Соберем результирующий эйлеров обход в порядке <tex>A1, B2, B1</tex> (без первой повторяющейся вершины), <tex>\{c\}A2</tex> в конец последовательности. [[Файл:Link2.png|thumb|400px |center]]

[[Файл:Link3Link22.png|thumb|400px|center|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]

В результате получимДля удаления ребра <tex>(g, j)</tex>:[[Файл*Найдем в эйлеровом обходе дерева <tex>T</tex> две пары посещений концов удаляемого ребра <tex>g,j</tex> и <tex>j,g</tex>, которые соответствуют прохождениям по ребру <tex>(g, j)</tex> в дереве <tex>T</tex>.*Разрежем эйлеров обход дерева по этим парам на три части:Cut3<tex>A1, A2, A3</tex>.*Соединив <tex>A1</tex> и <tex>A3</tex> (без повторяющейся первой вершины), получим эйлеров обход первого дерева, а <tex>A2</tex> дает эйлеров обход второго дерева.png|thumb|350px|center]]

{{Задача[[Файл:Link23.png |definition = Определить структуру данных thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлеровых обходов эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев для наиболее эффективного выполнения указанных операций.}}]]

При представлении деревьев ===Проверка на связность===Для того, чтобы проверить, лежат ли две вершины в виде их эйлерова обхода выполнение одном дереве, достаточно подняться от вхождения каждой операции <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex> сводится к <tex>Oвершины в эйлеров обход (1ссылку на которое мы храним)</tex> соединений и разбиений отрезков в последовательности вершин эйлерова обходадо корня дерева поиска, хранящего этот эйлеров обход.

Рассмотрим следующие ==Способы реализации структуры данных для определения времени выполнения разбиения и соединения последовательностей, а также определение принадлежности вершин одной компоненте связности.==

===Связные спискиСбалансированное дерево поиска===

Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Файл:Linked lists.png Красно-черное дерево|centerкрасно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.

Для каждой вершины будем Также, можем хранить указатели на первое и последнее вхождение вершины последовательности вершин эйлерова обхода в последовательность[[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Тогда возможно определять первое и последнее вхождение вершины за Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, будет поддерживаться равной <tex>O(1\log n)</tex>.

Однако,используя [[Список|двусвязные списки]] определение принадлежности вершин одной компоненте связности занимает <tex>O(\log n)</tex> в худшем случае. ===Balanced Trees===[[Файл:Balanced tree.png |center|Пример ]] Представим последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева. Будем использовать [[Красно-черное дерево|красно-черное дерево]]. Объединение Операции объединения и разделение красно-черных деревьев выполняется разделения также выполняются за <tex>O(\log n)</tex>.  Для каждой вершины храним указатели на её первое и последнее вхождение в последовательность. Значит, имеем доступ к ним за <tex>O(1)</tex>. Запрос о принадлежности вершин к одной компоненте связности выполняется за <tex>O(\log n)</tex> проверкой лежат ли эти вершины в одном дереве. [[Файл:Balanced tree1.png |center|Пример ]]