Изменения

Задача о наименьшем общем предке для двух вершин в дереве с <tex>n</tex> вершинами решается с помощью heavy-light декомпозиции. Воспользуемся основной идеей: декомпозиция разбивает все вершины дерева на вершинно-непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log{n}</tex> различных путей.

Построим декомпозицию. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:

# Расстояние до корня дерева. <br />Вычисляется за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину.

# Номер вершины, в которую выходит первое ребро пути, ведущего из предка в вершину. <br />Находится за <tex>O(1)</tex> при построении.

Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, <tex>v</tex>, пусть <tex>s</tex> {{---}} предок вершины <tex> u</tex>, а <tex> t</tex> {{---}} предок вершины <tex>v</tex>.

Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем LCA.

<code>

</code>

* '''Память''': Для реализации алгоритма требуется <tex>O(n)</tex> памяти.

* '''Препроцессинг''': Heavy-light декомпозиция строится за <tex>O(n)</tex>.