102
правки
Изменения
Нет описания правки
Задача о наименьшем общем предке для двух вершин в дереве с <tex>n</tex> вершинами решается с помощью Heavy-light декомпозиции за время <tex>O(\log{n})</tex>.
Мы можем проверять, что вершина является предком другой вершины за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину. Тогда рассмотрим самый нижний путь (содержащий первую вершину) и посмотрим на его корень (самая высокая вершина в пути). Если эта вершина является предком второй вершины, то ответ где-то в этом пути, иначе выкинем этот путь и рассмотрим следующий вверх за нимсверху путь.
Когда мы определили путь, в котором содержится ответ, мы можем с помощью бинпоиска найти в нём первую вершину, являющуюся предком второй вершины. Эта вершина является ответом.
