==Операции c эйлеровыми обходами==
Представление деревьев в виде их эйлеровых обходов позволяет свести задачу о динамической связности к следующим операциям с последовательностями вершин:
===Изменение корня дерева (переподвешивание)===
Дано дерево с корнем в вершине <tex>a</tex>. Требуется переподвесить его к вершине <tex>h</tex>.
[[Файл:Tour14.png |thumb|320px|center]]
Для переподвешивания (англ. ''rerooting'') необходимо:
*Разбить эйлеров обход на три части:
*: <tex>S1</tex> - вершины, посещенные эйлеровым обходом до захода в <tex>h</tex>.
*: <tex>H</tex> - вершины между первым и последним вхождением нового корня <tex>h</tex>.
*: <tex>S2 </tex> - вершины, посещенные эйлеровым обходом после выхода из <tex>h</tex>.
*Удалить первую вершину в <tex>S1 </tex>.
*Соединить в следующем порядке: <tex>H</tex>, <tex>S2 </tex>, <tex>S1 </tex>.
*Добавить <tex>\{h\}</tex> в конец последовательности.
[[Файл:Tour13.png |thumb|320px|center]]
В результате получим:
[[Файл:Proba.png |center]]
===Добавление ребра===
[[Файл:Link11.png |thumb|400px|center]]
Для связывания деревьев <tex>T1 </tex> и <tex>T2</tex>, где <tex>c\in T1\ </tex>, а <tex>g\in T2\</tex> добавлением ребра Пусть хотим добавить ребро <tex>\{c, g\} \</tex> необходимо:*Переподвесить дерево Выберем любое вхождение вершины <tex>T1с</tex> к вершине в эйлеров обход T1Разрежем эйлеров обход T1 на 2 частиA1 - часть обхода до выбранного вхождения вершины <tex>cс</tex>, если корнем дерева была другая вершина.*Переподвесить дерево A2 - часть обхода после выбранного вхождения вершины <tex>T2с</tex> к вершине Аналогично, выберем любое вхождение вершины <tex>g</tex>, если корнем дерева была другая вершина.*Соединить получившиеся эйлеровы обходы.*Добавить <tex>\{c\}</tex> в конец последовательности. [[Файл:Link2.png|thumb|400px |center]]эйлеров обход T2 и разрежем его на 2 части B1 и B2 В результате получим Соберем результирующий эйлеров обход дерева с корнем в вершине <tex>c</tex>:порядке A1 B2 B1 A2
[[Файл:Link3Чтобы быстро находить место, где разрезать эйлеровы обходы T1 и T2, будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины, для построения дерева поиска, будет время посещения этой вершины эйлеровым обходом.Для каждой вершины дерева (T1, T2) будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за O(1) переходим от вершины дерева к вершине дерева поиска, по которой за O(log n) можно будет разделить дерево поиска на 2 части.png|center]]
===Разрезание ребра===
