E074. Heavy-light декомпозиция

Источник: e-maxx.ru/algo, страница PDF 222.

Heavy-light декомпозиция — это достаточно общий приём, который позволяет эффективно решать многие задачи, сводящиеся к запросам на дереве. Простейший 示例 задач такого вида — это следующая 题目. given 树, каждой вершине которого

приписано какое-то number. Поступают запросы вида

, где

и

— номера вершин дерева, и it is required

узнать максимальное number на пути между vertexми

и

.

Описание 算法а

Итак, пусть given 树

с

vertexми, подвешенное за некоторый корень. Суть этой декомпозиции в том, чтобы разбить 树 на несколько путей таким образом, чтобы

для любой вершины

получалось, что если мы будем подниматься от

к корню, то по пути сменим не более

путей. Кроме того, все пути должны не пересекаться друг с другом по рёбрам. Понятно, что если мы научимся искать такую декомпозицию для любого дерева, это позволит свести любой запрос

вида "узнать что-то на пути из

в

" к нескольким запросам вида "узнать что-то на отрезке

-го пути".

Построение heavy-light декомпозиции

Посчитаем для каждой вершины

размер её поддерева

(т.е. это количество вершин в поддереве вершины

, включая саму вершину). Далее, рассмотрим все рёбра, ведущие к сыновьям какой-либо вершины

. Назовём edge

тяжёлым, если

оно ведёт в вершину

такую, что: Все остальные рёбра назовём лёгкими. Очевидно, что из одной вершины

вниз может исходить максимум

одно тяжёлое edge (т.к. в противном случае у вершины

было бы два сына размера

, что с учётом

самой вершины

даёт размер

, т.е. пришли к противоречию). Теперь построим саму декомпозицию дерева на непересекающиеся пути. Рассмотрим все вершины, из которых не 输出ит вниз ни одного тяжёлого ребра, и будем идти от каждой из них вверх, пока не дойдём до корня дерева или не пройдём лёгкое edge. В результате мы получим несколько путей — покажем, что это и есть искомые пути heavy- light декомпозиции.

正确性证明 算法а

Во-первых, заметим, что полученные 算法ом пути будут непересекающимися. В самом деле, если бы два каких-то пути имели бы общее edge, это бы означало, что из какой-то вершины исходит вниз два тяжёлых ребра, чего быть не может. Во-вторых, покажем, что спускаясь от корня дерева до произвольной вершины, мы сменим по пути не

более

путей. В самом деле, проход вниз по лёгкому ребру уменьшает размер текущего поддерева более чем вдвое:

Таким образом, мы не могли пройти более

лёгких рёбер. Однако переходить с одного пути на другой мы

можем только через лёгкое edge (т.к. каждый путь, кроме заканчивающихся в корне, содержит лёгкое edge в конце; а попасть сразу посередине пути мы не можем). Следовательно, по пути от корня до любой вершины мы не можем сменить более

путей, что и

требовалось доказать.

Applications при решении задач

При решении задач иногда бывает удобнее рассматривать heavy-light как набор вершинно-непересекающихся путей (а не рёберо-непересекающихся). Для этого достаточно из каждого пути исключить последнее edge, если оно являются лёгким edgeм — тогда никакие свойства не нарушатся, но теперь каждая vertex будет принадлежать ровно одному пути. Ниже мы рассмотрим несколько типичных задач, которые можно решать с помощью heavy-light декомпозиции. Отдельно стоит обратить внимание на задачу сумма чисел на пути, поскольку это 示例 задачи, которая может быть решена и более простыми техниками.

Максимальное number на пути между двумя vertexми

given 树, каждой вершине которого приписано какое-то number. Поступают запросы вида

, где

и

—

номера вершин дерева, и it is required узнать максимальное number на пути между vertexми

и

. Построим заранее heavy-light декомпозицию. Над каждым получившимся путём построим Segment tree для максимума, что позволит искать вершину с максимальным приписанным numberм в указанном сегменте указанного пути

за

. Хотя number путей в heavy-light декомпозиции может достигать

, суммарный размер всех путей

есть величина

, поэтому и суммарный размер деревьев отрезков также будет линейным.

Теперь, для того чтобы отвечать на поступивший запрос

найдём наименьшего общего предка

этих

вершин (на示例, методом двоичного подъёма). Теперь 题目 свелась к двум запросам:

и

, на каждый

из которых мы можем ответить таким образом: найдём, в каком пути лежит нижняя vertex, сделаем запрос к этому пути, перейдём в вершину-конец этого пути, снова определим, в каком мы пути оказались и сделаем запрос к нему, и

так далее, пока не дойдём до пути, содержащего

.

Аккуратно следует быть со случаем, когда, на示例,

и

оказались в одном пути — тогда запрос максимума к этому

пути надо делать не на суффиксе, а на внутреннем подотрезке. Таким образом, в процессе ответа на один подзапрос мы пройдём по

путям, в каждом из них сделав

запрос максимума на суффиксе или на префиксе/подотрезке (запрос на префиксе/подотрезке мог быть только один раз).

Так мы получили 解法 за

на один запрос. Если ещё дополнительно предпосчитать на каждом пути максимумы на всех суффиксах, то получится 解法

за

— т.к. запрос максимума не на суффиксе случается только один раз, когда мы доходим до вершины .

Сумма чисел на пути между двумя vertexми

given 树, каждой вершине которого приписано какое-то number. Поступают запросы вида

, где

и

—

номера вершин дерева, и it is required узнать сумму чисел на пути между vertexми

и

. Возможен вариант этой

задачи, когда дополнительно бывают запросы изменения числа, приписанного той или иной вершине. Хотя эту задачу можно решать с помощью heavy-light декомпозиции, построив над каждым путём Segment tree для суммы (или просто предпосчитав частичные суммы, если в задаче отсутствуют запросы изменения), эта 题目 может быть решена более простыми техниками. Если запросы модификации отсутствуют, то узнавать сумму на пути между двумя vertexми можно параллельно с поиском LCA двух вершин в 算法е двоичного подъёма — для этого достаточно во время препроцессинга для

LCA подсчитывать не только

-ых предков каждой вершины, но и сумму чисел на пути до этого предка. Есть и принципиально другой подход к этой задаче — рассмотреть эйлеров обход дерева, и построить Segment tree над ним. Этот 算法 рассматривается в статье с 解法м похожей задачи. (А если запросы модификации отсутствуют — то достаточно обойтись предпосчётом частичных сумм, без дерева отрезков.) Оба этих способа дают относительно простые решения с асимптотикой на один запрос.

Перекраска рёбер пути между двумя vertexми

given 树, каждое edge изначально покрашено в белый цвет. Поступают запросы вида

, где

и

—

номера вершин,

— цвет, что означает, что все рёбра на пути из

в

надо перекрасить в цвет

. it is required после

всех перекрашиваний сообщить, сколько в итоге получилось рёбер каждого цвета. 解法 — просто сделать Segment tree с покраской на отрезке над набором путей heavy-light декомпозиции.

Каждый запрос перекраски на пути

превратится в два подзапроса

и

, где

— наименьший

общий предок вершин

и

(найденный, на示例, 算法ом двоичного подъёма), а каждый из этих подзапросов —

в

запросов к деревьям отрезков над путями.

Итого получается 解法 с асимптотикой

на один запрос.

Задачи в online judges

Список задач, которые можно решить, используя heavy-light декомпозицию:

● TIMUS #1553 "Caves and Tunnels" [Complexity: средняя]

● IPSC 2009 L "Let there be rainbows!" [Complexity: средняя]

● SPOJ #2798 "Query on a tree again!" [Complexity: средняя]

● Codeforces Beta Round #88 E "树 или не 树" [Complexity: высокая]