1632
правки
Изменения
м
<code>
</code>
<code> '''int''' query('''int''' u, '''int''' v):
</code>
rollbackEdits.php mass rollback
</ul>
Множество подобных запросов делаются за время за полином от логарифма (обычно <tex>O(\log^2{n})</tex>) с помощью Heavyheavy-light декомпозиции.
==Описание декомпозиции==
[[Файл:Heavylight.png|thumb|right|800x280px|Пример разбиения. В вершинах указан размер поддерева.]]
Необходимо составить такую декомпозицию дерева на множество рёберно-непересекающихся путей, что при прохождении от одной вершины до другой произойдет смена не более <tex>O(\log{n})</tex> путей из декомпозиции.
Декомпозиция заключается в классификации всех рёбер дерева <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> путей.
}}
Существует вариант Heavyheavy-light декомпозиции на вершинно-непересекающихся путях. Чтобы получить такой путь нужно всего-лишь выкинуть последнее ребро из всех путей в рёберно-непересекающейся декомпозиции. Это может быть удобно при решении задач, где веса находятся не на рёбрах, а на вершинах и соответствующие запросы также делаются на вершинах.
==Применение==
===Сумма на пути===
Классическая задача о сумме на пути в дереве с <tex>n</tex> вершинами может быть решена с помощью Heavyheavy-light декомпозиции за время <tex>O(\log^2{n})</tex>. Возможны модификации веса.
Построим [[Дерево отрезков. Построение|дерево отрезков]] над каждым путём. Рассмотрим запрос <tex>sum(u, v)</tex>. Найдем вершину <tex>c</tex>, которая является <tex>\mathrm{LCA}(u, v)</tex> (например с помощью [[Метод двоичного подъема|двоичного подъема]]. Мы разбили запрос на два: <tex>(u, c)</tex> и <tex>(c, v)</tex>, на каждый из которых можно легко ответить разбив его на множество путей из декомпозиции и ответив на каждый путь из этого множества по отдельности за <tex>O(\log{n})</tex> с помощью дерева отрезков на этом пути. Всего таких путей нужно будет рассмотреть <tex>O(\log{n})</tex>. Итого мы способны решить эту задачу за время <tex>O(\log^2{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>.
# Вторая вершина этого пути. <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)
====Асимптотика====
</ul>
Пример реализации запроса суммы на пути:
'''int''' res = 0
'''int''' root = корень пути, в котором находится u
'''while''' root не является предком v <font color=green> // поднимаемся до тех пор, пока наш путь не содержит общего предка u и v</font>
segmentTree = дерево отрезков, соответствующее пути, в котором лежит u
res += segmentTree.sum(0, pathPos(u))
u = предок root <font color=green> // вырезали нижний путь и подняли нижнюю вершину до нижней вершины следующего пути</font>
root = корень пути, в котором находится u
root = корень пути, в котором находится v
'''while''' root не является предком u <font color=green> // аналогично прошлому while, но с другой стороны</font>
segmentTree = дерево отрезков, соответствующее пути, в котором лежит v
res += segmentTree.sum(0, pathPos(v))
v = предок root
root = корень пути, в котором находится v
<font color=green>// последний путь (тот, что содержит общего предка) обрезан с двух сторон полученными вершинами</font>
segmentTree = дерево отрезков, соответствующее пути в котором лежит u
res += segmentTree.sum(min(pathPos(u), pathPos(v)), max(pathPos(u), pathPos(v)))
'''return''' res
== См.также ==
