LCA и запросы на пути между вершинами с изменением весов рёбер и вершин

Тайм-коды: 00:00:00 Введение 00:01:55 Что такое LCA (наименьший общий предок)? 00:07:40 Пример задачи: расстояние между двумя вершинами 00:15:15 Разница между offline и online запросами 00:20:25 LCA Offline: отвечаем на все запросы за один поиск в глубину 00:24:40 Является ли одна вершина предком другой вершины? 00:29:20 Добиваем задачу о расстояниях первым способом 00:30:30 Двоичные прыжки: другой способ вычисления LCA 00:36:40 Алгоритм нахождения LCA двоичными прыжками 00:43:40 Запросы на добавление новых листьев и удаление существующих 00:48:25 Разбираем реализацию LCA offline на C 00:56:30 Разбираем реализацию двоичных прыжков на C 01:02:05 Двоичный логарифм и единичные биты 01:11:10 Разговоры о строках в стиле Си 01:16:10 Возвращаемся к разбору двоичных прыжков 01:18:40 Минимум на пути, максимум, ксор, сумма (без модификаций) 01:21:30 Задача “Мегашустрый LCA online“ 01:23:40 Ускорение двоичных прыжков в 2 раза 01:29:45 Как считать LCA за O(1) 01:34:30 Эйлеров обход всех рёбер 01:42:00 Прибавление веса к ребру и сумма на пути между двумя вершинами 01:44:00 Числа в вершинах и числа на рёбрах: в чём разница 01:48:00 Как считать сумму на пути через сумму на отрезках и LCA 01:51:10 Прибавление и присваение весов рёбер