Заголовок.

# Link-Cut tree

## Основа

- Покрытие дерева путями
- Хранение пути в виде декартова дерева
- Сделать вершину корнем
- Ответ на запрос "функция на пути от v до корня" за O(klogn), где k число прыжков

## Link-Cut

- Expose
- MakeRoot
- Link
- Cut
- Get(a, b)

## Подробная реализация

- Что нам нужно от декаротва дерева?
- Как мы делаем Expose?
- Как мы делаем MakeRoot

## Доказательство корректности

- Потенциал = количество тяжёлых рёбер, покрытых путями
- Изменение потенциала при Expose
- Изменение потенциала при Reverse
- Изменение потенциала при Link и Cut

## Splay-Tree

- Splay
- Теорема про время работы без доказательства
- Соединяем с Link-Cut tree