Heavy-Light decomposition (3 марта 2016)

1. Задача: сумма на пути, изменение в точке [O(n), O(logn)]
2. Задачи (и разбор задач контеста)
1. Переподвесить дерево, запрос LCA, online
2. Дано дерево и число k. Найти за O(n) для каждой вершины v: up[v,k].
3. Добавляются листья. Отвечать на запрос "размер поддерева". Offline, online.
4. Euler tour tree: makeRoot (поменять корень), link (добавить ребро), cut (удалить ребро), isConnected (связны ли две вершины)
5. Дан неориентированный взвешенный граф. Найти промежуток весов [l,r]: |r-l| → max, а рёбра с такими весами не образуют циклы
6. Много запросов вида += на пути. В конце сказать веса всех вершин. O(m×LCA+n).
7. Дано дерево, в вершинах стоят нули. Появляются единицы. Нужно говорить ближайший сверху ноль, ближайшую сверху единицу. Offline, online.
3. Кодим Heavy-Light decomposition [code]
1. Разбиение дерева на пути. Интерфейс структуры для пути.
2. Добавляем для пути дерево отрезков.
3. Добавляем кеширование запросов
4. Задачи на Heavy-Light decomposition
1. Запрос: найти число ≥ X, ближнее к вершине A на пути к вершине B. Версия, когда веса не меняются (делается без Heavy-Light), и когда веса меняются.
2. Изменение в точке, минимум на пути в дереве.
3. += на пути дерева, минимум на пути в дереве.