286
правок
Изменения
→LCA
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в <tex>2</tex> вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>.
'''Тяжёлые ребра''' (англ. ''heavy edge'') {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geqslant</tex> <tex dpi="150">\fracdfrac{s(u)}{2}</tex>.
'''Лёгкие ребра''' (англ. ''light edge'') {{---}} соответственно все остальные.
Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум <tex dpi="150">\fracdfrac{s(u)}{2}</tex> вершин, а также сама вершина <tex>u</tex>. Итого <tex>s(u) + 1</tex> вершин, тогда как у нас всего <tex>s(u)</tex> вершин в поддереве.
Теперь рассмотрим вершины, из которых не ведет вниз ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что полученная таким образом декомпозиция будет являться искомой и корректной.
Докажем по отдельности корректность декомпозиции.
# Все рёбра покрыты путями. <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}(u, v)</tex> не равныи <tex>\mathrm{LCA}(U, v)</tex> это разные вершины. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
Теперь рассмотрим случай, когда пути пересекаются. Пути не могут совпадать более, чем в одной вершине, так как построенная декомпозиция является реберно-непересекающейся. При этом корень одного из путей является вершиной другого (либо корни совпадают, что равносильно), поскольку в противном случае пути пересекаются в более чем <tex>1</tex> вершине, что противоречит предыдущему условию. <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, значит именно этот корень и будет <tex>\mathrm{LCA}</tex>.
====Препроцессинг====
Построим heavy-light декомпозицию для данного нам дерева. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
# Расстояние до корня дерева. <br />Вычисляется за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину.
# Корень пути, на котором лежит вершина. <br /> Поскольку вершина может принадлежать нескольким путям, выберем тот, чья начальная вершина наиболее удалена от корня дерева. Имея разбиение на пути, найти корень можно за <tex>O(1)</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
