Изменения
Нет описания правки
Динамические деревья (англ. ''link-cut trees'') используются в двух областях: [[Определение сети, потока|потоки ]] и динамические графы.
В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока.
В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Изменения нужно быстро обрабатывать, а также уметь [[Отношение связности, компоненты связности | проверять связность]], [[Алгоритмы на деревьях|искать диаметр]]. Динамические деревья являются инструментом, который позволяет легко решать эти задачи. Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов '''link''' и '''cut'''.
'''Link-cut tree''' {{---}} это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:
