Изменения

Перейти к: навигация, поиск

Метод двоичного подъёма

493 байта добавлено, 21:35, 7 мая 2016
Модификация предподсчета за 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>
# <font color=darkgreen>// Находит наименьшего общего предка вершин '''u''' и '''v'''</font> '''defint''' lca('''int''' u, '''int''' v): # <font color=darkgreen>// Проверяем вершины, в которые идут ребра из предков.</font>
'''if''' (turn[u] == turn[v]):
# <font color=darkgreen>// Ответ найден, выберем ближайшую к корню.</font>
'''if''' (dist[u] < dist[v]):
'''return''' u
'''else''':
'''return''' v
# <font color=darkgreen>// Приблизимся к корню. Выбираем наиболее удаленную вершину.</font>
'''if''' (dist[last[u]] > dist[last[v]]):
'''return''' lca(last[u], v)
Анонимный участник

Навигация