Изменения

Множество подобных запросов делаются за время за полином от логарифма (обычно <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> различных путей. {{Лемма|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> при построении.

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

Пусть вершина <tex>A</tex> {{---}} первая вершина пути из предка вершины <tex>u</tex> в вершину <tex>u</tex>Для проверки этого условия недостаточно знать только корни путей, а <tex>B</tex> {{---}} первая вершина потому что несколько путей могу иметь общий корень. Но любые два пути из предка вершины<tex>v</tex> пересекаются не более чем в вершину <tex>v</tex>одной вершине. Воспользуемся этим фактом.

Сравним вершины Пусть <tex>Aa</tex>, и <tex>Bb</tex>: * <tex>A</tex> = <tex>B</tex>. <br />Или {{---}} вторые вершины путей, содержащих вершины <tex>u</tex> лежит на пути от корня к и <tex>v</tex>соответственно. Важно заметить, что любая вершина, или наоборот. За LCA примем ту вершинупомимо корня дерева является некорневой вершиной какого-либо другого пути, которая лежит ближе к корню.* поэтому такие <tex>Aa</tex> и <tex>\not=b</tex> <tex>B</tex>.<br />Нужно приблизить одну из вершин к корню, выбрав вместо нее её предка. Приближать будем на основании того, какая из вершин останется дальше от корня, после приближениявсегда существуют.

* Если это не так, то вершины лежат на разных путях. По лемме, так как пути реберно не пересекаются, то ответ не изменится, если вместо одной из вершин взять корень того пути, на котором она лежит. Эту операцию будем производить с той вершиной, чей предок наиболее удален от корня. Рекурсивно запустимся от выбранной и оставшейся вершин. Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем <tex>\mathrm{LCA}</tex>.

Объявим несколько массивов для хранения дополнительной информации:* <tex>\mathtt{dist}</tex> {{---}} расстояние от корня до вершины.* <codetex>\mathtt{last}</tex> {{---}} начало пути, на котором лежит вершина. Из всех путей выбирается путь с самой удаленной от корня дерева начальной вершины.* <tex>\mathtt{turn}</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]):

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

'''else''':

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

====АссимптотикаАсимптотика====* '''Память''': Для для реализации алгоритма требуется <tex>O(n)</tex> памяти.* '''Препроцессинг''': Heavyheavy-light декомпозиция строится за <tex>O(n)</tex>, вся дополнительная информация считается за <tex>O(1)</tex> для каждой из вершин.* '''Запросы''': По по свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более <tex>\log n</tex> путей. Значит время выполнения запроса также <tex>O(\log n)</tex>.

<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>