Изменения

Множество подобных запросов делаются за время за полином от логарифма (обычно <tex>O(\log^2{n})</tex>) с помощью Heavyheavy-light декомпозиции.

Декомпозиция заключается в классификации всех рёбер дерева <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>.

Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум <tex dpi="150">\fracdfrac{s(u)}{2}</tex> вершин, а также сама вершина <tex>u</tex>. Итого <tex>s(u) + 1</tex> вершин, тогда как у нас всего <tex>s(u)</tex> вершин в поддереве.

# Все пути не пересекаются. <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>.

Задача о наименьшем общем предке для двух вершин в дереве с <tex>n</tex> вершинами решается также может быть решена с помощью heavy-light декомпозиции. Воспользуемся основной идеей: декомпозиция разбивает все вершины дерева на реберно-непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log{n}</tex> различных путей.

|statement=Пусть есть две вершины <tex>au</tex>, и <tex>bv</tex>, лежащие на разных путях. Пусть При этом <tex>AU</tex>, <tex>BV</tex> - — корни путей, на которых они лежат. Пусть Если <tex>AU</tex> более удален от корнядерева, чем <tex>BV</tex>. Докажем, что то <tex>\mathrm{LCA}(au, bv) </tex> = <tex>\mathrm{LCA}(AU, Bv)</tex>.

|proof=Пусть Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}(u, v)</tex> и <tex>\mathrm{LCA не равны}(U, v)</tex> это разные вершины. Значит Тогда существует вершина, на пути от <tex>au</tex> к <tex>AU</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>.

Пусть требуется найти Найдем <tex>\mathrm{LCA }</tex> для двух вершин. Для этого будем рекурсивно подниматься от этих вершин в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, и <tex>v</tex>. Заметим, что если эти вершины лежат на одном пути, то мы нашли ответ: LCA будет та{{---}} это такая вершина (<tex>u</tex> или <tex>v</tex>), которая находится ближе к корню, т.е расстояние от корня до которой минимально. Очевидно, что если расстояние от корня до <tex>u</tex> до корня меньше, чем расстояние от до <tex>v</tex> до корня, то <tex>u</tex> является предком <tex>bv</tex>. Иначе, а не наоборот.

Для проверки этого условия недостаточно знать только корни путей. Потому , потому что бесконечно большое количество несколько путей могу иметь общий корень. Но любые два пути пересекаются не более чем в одной вершине. Воспользуемся этим фактом.

* Заметим, что если <tex>a</tex> = <tex>b</tex>, то или <tex>u</tex> лежит на пути от корня к и <tex>v</tex>, или наоборотлежат на одном пути. Этот случай мы уже рассмотрели ранее.

* Если это не так, то вершины лежат на разных путях. По лемме, т.к так как пути реберно не пересекаются, то ответ не изменится, если вместо одной из вершин взять корень того пути, на котором она лежит. Эту операцию будем производить с той вершиной, чей предок наиболее удален от корня. Рекурсивно запустимся от выбранной и оставшейся вершин.

 Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем <tex>\mathrm{LCA}</tex>.

'''int''' lca('''int''' u, '''int''' v):

'''if''' (turn[u] == turn[v]):

'''if''' (dist[u] < dist[v]):

'''else''':

<font color=darkgreen>// Рекурсивно запустимся от вершины, чей предок наиболее удален от корнядерева.</font> '''if''' (dist[last[u]] > dist[last[v]]):

====АссимптотикаАсимптотика====

<code> '''int''' query('''int''' u, '''int''' v):

'''while''' root не является предком v <font color=green> // поднимаемся до тех пор, пока наш путь не содержит общего предка u и v</font>

u = предок root <font color=green> // вырезали нижний путь и подняли нижнюю вершину до нижней вершины следующего пути</font>

'''while''' root не является предком u <font color=green> // аналогично прошлому while, но с другой стороны</font>