286
правок
Изменения
Нет описания правки
Докажем по отдельности корректность декомпозиции.
# Все рёбра покрыты путями. <br>Есть два типа вершин: те, из которых ведёт ровно одно тяжёлое ребро и те, из которых не ведёт ни одного тяжёлого ребра. Для первого типа вершин мы дойдем до них некоторым путём через тяжёлое ребро снизу по определению выбора путей, а лёгкие рёбра ведущие из неё возьмем как последние рёбра в соответствующих путях. Для второго типа вершин мы по определению выбора путей возьмем их как начальные и пойдем вверх. <br>Таким образом все рёбра будут покрыты.
# Все пути не пересекаются. <br>Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины вело <tex>v</tex> ведет более чем одно тяжёлое <tex>1</tex> тяжелого ребра в детей. Эти ребра относятся к разным путями, однако пути имеют хотя бы общее ребро {{---}} реброиз <tex>v</tex> в отца <tex>v</tex>. Более <tex>1</tex> тяжелого ребра из вершины идти не может, чего быть не могло. Получили следовательно получили противоречие.
# При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей. <br>Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в <tex>2</tex> раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.
}}
{{Лемма
|id=Лемма1
|statement=Пусть есть вершины <tex>u</tex> и <tex>v</tex>, лежащие на разных путях. При этом <tex>U</tex>, <tex>V</tex> — корни путей, на которых они лежат. Если <tex>U</tex> более удален от корнядерева, чем <tex>V</tex>, то <tex>\mathrm{LCA}(u, v) = \mathrm{LCA}(U, v)</tex>.
|proof=Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}</tex> не равны. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
<font color=darkgreen>// Находит наименьшего общего предка вершин <tex>u</tex> и <tex>v</tex></font>
'''int''' lca('''int''' u, '''int''' v):
<font color=darkgreen>// Проверяем вторые вершины путей, содержащих <tex>u</tex> и <tex>v</tex>.</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)
'''return''' lca(last[v], u)
Пример реализации запроса суммы на пути:
'''int''' query('''int''' u, '''int''' v):
'''int''' res = 0
'''int''' root = корень пути, в котором находится u
