Изменения
→Модификация предподсчета за O(n) времени и O(n) памяти
</code>
==Модификация предподсчета за <tex>O(n)</tex> времени и <tex>O(n)</tex> памяти==
Воспользуемся идеей [[Heavy-light декомпозиция|Heavy-light декомпозиции]], которая разбивает все вершины дерева на вершинно -непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log(n)</tex> различных путей.
===Препроцессинг===
Построим декомпозицию, для каждой вершины, помимо ее предка будем хранить дополнительно следующие значения:
# Расстояние до корня дерева.
# Номер предка. (Начало {{---}} начало пути от корня, ведущего в вершину).# Номер вершины, в которую выходит первое ребро пути, ведущего из предка, ведущее в вершину.
===Вычисление LCA===
Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>Uu</tex>, <tex>v</tex>, пусть <tex>s</tex> {{---}} предок вершины <tex> u</tex>, а <tex> t</tex> {{---}} предок вершины <tex>v</tex>. Рассмотрим пути из <tex>s</tex> в <tex>u</tex> и из <tex>t</tex> в <tex>u</tex>.Пусть вершина <tex>A</tex> {{---}} первая вершина пути из <tex>s</tex> в <tex>u</tex>, а <tex>VB</tex> {{---}} первая вершина пути из <tex>t</tex> в <tex>u</tex>. Сравним вершины (<tex>A</tex>, <tex>B</tex>), в которые идут ребра из предков рассматриваемых вершин. : * <tex>A</tex> = <tex>B</tex>. <br />Или <tex>U</tex> лежит на пути от корня к <tex>V</tex>, или наоборот. За LCA выберем примем ту вершину, которая лежит ближе к корню.* <tex>A</tex> <tex>\not=</tex> <tex>B</tex>. <br />Нужно приблизить одну из вершин к корню, выбрав вместо нее её предка. Приближать будем на основании того, какая из вершин останется дальше от корня, после приближения.
Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем LCA.
<code>
'''if''' (turn[u] == turn[v]):
'''if''' (dist[u] < dist[v]):
'''return''' u
'''else''':
'''return''' v
'''if''' (dist[last[u]] > dist[last[v]]):
'''return''' lca(last[u], v)