102
правки
Изменения
Нет описания правки
==Описание задачи==
{{Задача
|definition=Имеется подвешенное дерево <tex>T</tex> c <tex>n</tex> вершинами и необходимо проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>.}}
Примеры запросов:
<ul>
<li>Сумма сумма на пути,</li><li>Максимум максимум на пути,</li><li>Количество количество рёбер на пути, вес которых больше заданного <tex>c</tex>.</li>
</ul>
Примеры модификаций:
<ul>
<li>Модификация модификация одного ребра,</li><li>Прибавление прибавление к весу всех рёбер на пути,</li><li>Установка установка веса всех рёбер на пути в заданное <tex>c</tex>.</li>
</ul>
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>.
'''Тяжёлые ребра ''' (Heavy англ. ''heavy edge)''' ) {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geqslant</tex> <tex dpi="150">\frac{s(u)}{2}</tex>.
'''Лёгкие ребра ''' (Light англ. ''light edge)''' ) {{---}} соответственно все остальные.
Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум <tex dpi="150">\frac{s(u)}{2}</tex> вершин, а также сама вершина <tex>u</tex>. Итого <tex>s(u) + 1</tex> вершин, тогда как у нас всего <tex>s(u)</tex> вершин в поддереве.
==Применение==
===Сумма на пути===
Классическая задача о сумме на пути в дереве с <tex>n</tex> решается с помощью Heavy-light декомпозиции за время<tex>O(\log^2{n})</tex>. Возможны модификации веса.
Построим [[Дерево отрезков. Построение|дерево отрезков]] над каждым путём. Рассмотрим запрос <tex>sum(u, v)</tex>. Давайте найдем вершину <tex>c</tex>, которая является <tex>LCA(u, v)</tex> (например с помощью [[Метод двоичного подъема|двоичного подъема]]. Мы разбили запрос на два: <tex>(u, c)</tex> и <tex>(c, v)</tex>, на каждый из которых можно легко ответить выбирая путь, содержащий самую нижнюю вершину и вырезать его, пока этот путь не содержит <tex>c</tex>.
Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что с помощью такого трюка мы можем решить широкий класс задач просто сведя её к задаче о запросах в дереве отрезков (такие как максимум на пути, покраска на пути, прибавление на пути и др.).
===LCA===
Задача о наименьшем общем предке для двух вершин в дереве с <tex>n</tex> решается с помощью Heavy-light декомпозиции за время <tex>O(\log{n})</tex>.
Мы можем проверять, что вершина является предком другой вершины за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину. Тогда рассмотрим самый нижний путь (содержащий первую вершину) и посмотрим на его корень (самая высокая вершина в пути). Если эта вершина является предком второй вершины, то ответ где-то в этом пути, иначе выкинем этот путь и рассмотрим следующий вверх за ним.
Когда мы определили путь, в котором содержится ответ, мы можем с помощью бинпоиска найти в нём первую вершину, являющуюся предком второй вершины. Эта вершина является ответом.
Итого мы рассмотрели корень каждого пути за <tex>O(1)</tex>, а путей всего <tex>O(\log{n})</tex>. И в последнем пути один раз запустили бинпоиск, который отработал за <tex>O(\log{n})</tex>. Итоговая асимптотика <tex>O(\log{n})</tex>.
==Реализация==
Опущены некоторые детали реализации: построение и предподсчёт.
<ul>
<li><tex>\mathrm{getPath}</tex> {{---}} функция, позволяющая найти номер пути, относящийся к конкретной вершине.,</li> <li><tex>\mathrm{pathRoot}</tex> {{---}} функция, позволяющая найти корень пути (самую верхнюю вершину).,</li> <li><tex>\mathrm{pathPos}</tex> {{---}} функция, позволяющая найти смещение вершины в пути относительно корня пути.,</li>
<li><tex>\mathrm{getValue(\mathtt{i}, \mathtt{j})}</tex> {{---}} функция, позволяющая найти вес <tex>\mathtt{j}</tex>-ого ребра в <tex>\mathtt{i}</tex>-ом пути.</li>
</ul>
