Изменения
→Модификация предподсчета за O(n)
</code>
==Модификация предподсчета за O(n)времени и O(n) памяти==
Воспользуемся идеей Heavy-light декомпозиции, которая разбивает все вершины дерева на пути с одним важным свойством: поднимаясь от любой вершины до корня дерева придется сменить не более log(n) различных путей.
Для каждой вершины будем хранить следующие значения:
1) расстояние до корня дерева
2) количество потомков
3) предок (начало пути, на котором лежит вершина)
4) номер вершины, в которую выходит ребро из предка, ведущее в нашу вершину.
Все эти значения можно посчитать при построении декомпозиции.
Перейдем к вычислению LCA:
Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины U, V. Сначала сравним вершины, в которые идут ребра из предков этих вершин. Если они совпадают, то, очевидно, или U лежит на пути от V к корню, или V лежит на пути от U к корню. Значит одна из них и является искомой. Выберем ту, чье расстояние до корня минимально.
Иначе нужно приблизить одну из этих вершин к корню, выбрав вместо нее ее предка. Приближать будем на основании того, какая из вершин останется дальше от корня, после приближения.
Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути ток корня к другой. Тем самым мы найдем LCA.
==Ассимптотика==
Очевидно, что для реализации алгоритма требуется O(n) памяти. Heavy-light декомпозиция строится за O(n). По свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более log(n) путей. Значит время выполнения запроса также O(log(n)).
==См. также==
