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

1. Задачи (и разбор задач контеста)
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.
2. Кодим Heavy-Light decomposition [code]
1. Разбиение дерева на пути. Интерфейс структуры для пути.
2. Добавляем для пути дерево отрезков.
3. Добавляем кеширование запросов
3. Задачи на Heavy-Light decomposition
1. Запрос: найти число ≥ X, ближнее к вершине A на пути к вершине B. Версия, когда веса не меняются (делается без Heavy-Light), и когда веса меняются.
2. Изменение в точке, минимум на пути в дереве.
3. += на пути дерева, минимум на пути в дереве.
4. Дано дерево namespace-ов. Все переменный булевы. Чтобы находясь в листе v узнать значение переменной x, нужно подниматься по дереву namespace-ов, пока не попадём в вершину, где x определена. Запросы: добавить запись (x,v,value); сказать, сколько у переменной x листьев со значением true/false/undefined.
4. Scanline
1. Разбор задачи про звёзды
2. Разбор задачи про наибольшую возрастающую подпоследовательность