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