LCA (16 февраля 2015)

  1. Задачи на LCA
    1. Задача #1: поиск LCA за O(расстояния между вершинами)
    2. Задача #2: сумма на пути в дереве (оно же − расстояние между вершинами)
  2. Двоичные подъёмы
    1. Пишем код для LCA за O(log2n) и O(logn) [code] , [code]
    2. Решаем минимум на пути дерева двоичными подъёмами
    3. Задача #1 "у каждой вершины v в графе есть next[v] — следующая вершина, научиться отвечать на запросы от вершины v сделать k ≤ 109 шагов".
    4. Задача #2 "на окружности даны N точек, выбрать максимальное количество точек на расстоянии хотя бы R друг от друга = два указателя + двоичные подъёмы"
    5. Задача #3 "появляются новые листья, пересчитывать двоичные подъёмы"
  3. Эйлеров обход дерева, времена входа выхода
    1. Кодим, отвечаем на запрос LCA через SparseTable [code]
    2. Задача #1. Обрабатывать два запроса: посчитать количество помеченных вершин в поддереве, поменять помеченность вершины.
    3. Задача #2. Веса рёбер меняются. Уметь отвечать на запрос "сумма на пути в дереве"
    4. Задача #3. Даны два дерева, вершины в обоих нумеруются 1..n. Запрос: по поддереву первого и поддереву второго сказать количество чисел от 1 до n, которые лежат и там, и там