Сайт использует сервис веб-аналитики Яндекс Метрика с помощью технологии «cookie». Пользуясь сайтом, вы даете согласие на использование данной технологии.
ЛКШ-2023, параллель 5. Лекция 12: Алгоритмы на корневых деревьях (LCA, LA и другие задачи).
Задача нахождения наименьшего общего предка (least common ancestor, LCA). Наивный алгоритм, двоичный подъём, сведение к RMQ, алгоритм Тарьяна для offline-задачи. Задача подъёма на заданную высоту (level ancestor problem, LA). Offline-решение при помощи DFS, двоичные подъёмы, решение при помощи long path decomposition и ladders. Другие задачи на деревьях, например, количество различных значений в поддеревьях offline.
