Перед прочтением статьи рекомендую посмотреть посты про splay-деревья (1) и деревья по неявному ключу (2, 3, 4)
![](https://habrastorage.org/getpro/habr/post_images/bc5/15c/2cc/bc515c2ccff0c451de00a7a446d863a3.png)
Динамические деревья (link/cut trees) мало освещены в русскоязычном интернете. Я нашел только краткое описание на алголисте. Тем не менее эта структура данных очень интересна. Она находится на стыке двух областей: потоки и динамические графы.
В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока. Улучшенные алгоритмы Диница и проталкивания предпотока работают за
![](https://habrastorage.org/getpro/habr/post_images/e8c/0e2/88d/e8c0e288d7f15babc7a91e9bed2a443c.gif)
и
![](https://habrastorage.org/getpro/habr/post_images/74b/2e9/dc6/74b2e9dc6cafd86699752ce073242a71.gif)
соответственно. Если вы не знаете, что такое поток, и на лекциях у вас такого не было, спешите пополнить свои знания в Кормене.
Второй случай требует небольшого введения. Динамические графы — это активно развивающаяся современная область алгоритмов. Представьте, что у вас есть граф. В нем периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Изменения нужно быстро обрабатывать, а еще уметь эффективно считать разные метрики, проверять связность, искать диаметр. Динамические деревья являются инструментом, который позволяет ловко манипулировать с частным случаем графов, деревьями.
Перед тем, как нырнуть под кат, попробуйте решить следующую задачу. Дан взвешенный граф в виде последовательности ребер. По последовательности можно пройти только один раз. Требуется посчитать минимальное покрывающее дерево, используя
![](https://habrastorage.org/getpro/habr/post_images/af1/17d/beb/af117dbeb11fc79d2dd596c0e8633a62.gif)
памяти и
![](https://habrastorage.org/getpro/habr/post_images/1a0/445/9d0/1a04459d0e4eda785ac9398ce61f213e.gif)
времени. По прочтении статьи вы поймете, как легко и просто можно решить эту задачу, используя динамические деревья.