MAXimal

добавлено: 6 Sep 2011 1:03
редактировано: 16 Nov 2011 23:48

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

Heavy-light декомпозиция — это достаточно общий приём, который позволяет эффективно решать многие задачи, сводящиеся к запросам на дереве.

Простейший пример задач такого вида — это следующая задача. Дано дерево, каждой вершине которого приписано какое-то число. Поступают запросы вида $(a,b)$ , где $a$ и $b$ — номера вершин дерева, и требуется узнать максимальное число на пути между вершинами $a$ и $b$ .

Описание алгоритма

Итак, пусть дано дерево $G$ с $n$ вершинами, подвешенное за некоторый корень.

Суть этой декомпозиции в том, чтобы разбить дерево на несколько путей таким образом, чтобы для любой вершины $v$ получалось, что если мы будем подниматься от $v$ к корню, то по пути сменим не более $\log n$ путей. Кроме того, все пути должны не пересекаться друг с другом по рёбрам.

Понятно, что если мы научимся искать такую декомпозицию для любого дерева, это позволит свести любой запрос вида "узнать что-то на пути из $a$ в $b$ " к нескольким запросам вида "узнать что-то на отрезке $[l;r]$ $k$ -го пути".

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

Посчитаем для каждой вершины $v$ размер её поддерева $s(v)$ (т.е. это количество вершин в поддереве вершины $v$ , включая саму вершину).

Далее, рассмотрим все рёбра, ведущие к сыновьям какой-либо вершины $v$ . Назовём ребро $(v,c)$ тяжёлым, если оно ведёт в вершину $c$ такую, что:

$s(c) \ge \frac{ s(v) }{ 2 } ~~~~ \Leftrightarrow [...]$

Все остальные рёбра назовём лёгкими. Очевидно, что из одной вершины $v$ вниз может исходить максимум одно тяжёлое ребро (т.к. в противном случае у вершины $v$ было бы два сына размера $s(v)/2$ , что с учётом самой вершины $v$ даёт размер $2 \cdot s(v) / 2 + 1 > s(v)$ , т.е. пришли к противоречию).

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

Доказательство корректности алгоритма

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

Во-вторых, покажем, что спускаясь от корня дерева до произвольной вершины, мы сменим по пути не более $\log n$ путей. В самом деле, проход вниз по лёгкому ребру уменьшает размер текущего поддерева более чем вдвое:

$s(c) < \frac{ s(v) }{ 2 } ~~~~ \Leftrightarrow ~~[...]$

Таким образом, мы не могли пройти более $\log n$ лёгких рёбер. Однако переходить с одного пути на другой мы можем только через лёгкое ребро (т.к. каждый путь, кроме заканчивающихся в корне, содержит лёгкое ребро в конце; а попасть сразу посередине пути мы не можем).

Следовательно, по пути от корня до любой вершины мы не можем сменить более $\log n$ путей, что и требовалось доказать.

Применения при решении задач

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

Ниже мы рассмотрим несколько типичных задач, которые можно решать с помощью heavy-light декомпозиции.

Отдельно стоит обратить внимание на задачу сумма чисел на пути, поскольку это пример задачи, которая может быть решена и более простыми техниками.

Максимальное число на пути между двумя вершинами

Дано дерево, каждой вершине которого приписано какое-то число. Поступают запросы вида $(a,b)$ , где $a$ и $b$ — номера вершин дерева, и требуется узнать максимальное число на пути между вершинами $a$ и $b$ .

Построим заранее heavy-light декомпозицию. Над каждым получившимся путём построим дерево отрезков для максимума, что позволит искать вершину с максимальным приписанным числом в указанном сегменте указанного пути за $O (\log n)$ . Хотя число путей в heavy-light декомпозиции может достигать $n-1$ , суммарный размер всех путей есть величина $O(n)$ , поэтому и суммарный размер деревьев отрезков также будет линейным.

Теперь, для того чтобы отвечать на поступивший запрос $(a,b)$ найдём наименьшего общего предка $l$ этих вершин (например, методом двоичного подъёма). Теперь задача свелась к двум запросам: $(a,l)$ и $(b,l)$ , на каждый из которых мы можем ответить таким образом: найдём, в каком пути лежит нижняя вершина, сделаем запрос к этому пути, перейдём в вершину-конец этого пути, снова определим, в каком мы пути оказались и сделаем запрос к нему, и так далее, пока не дойдём до пути, содержащего $l$ .

Аккуратно следует быть со случаем, когда, например, $a$ и $l$ оказались в одном пути — тогда запрос максимума к этому пути надо делать не на суффиксе, а на внутреннем подотрезке.

Таким образом, в процессе ответа на один подзапрос мы пройдём по $O (\log n)$ путям, в каждом из них сделав запрос максимума на суффиксе или на префиксе/подотрезке (запрос на префиксе/подотрезке мог быть только один раз).

Так мы получили решение за $O (\log^2 n)$ на один запрос.

Если ещё дополнительно предпосчитать на каждом пути максимумы на всех суффиксах, то получится решение за $O (n \log n)$ — т.к. запрос максимума не на суффиксе случается только один раз, когда мы доходим до вершины $l$ .

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

Дано дерево, каждой вершине которого приписано какое-то число. Поступают запросы вида $(a,b)$ , где $a$ и $b$ — номера вершин дерева, и требуется узнать сумму чисел на пути между вершинами $a$ и $b$ . Возможен вариант этой задачи, когда дополнительно бывают запросы изменения числа, приписанного той или иной вершине.

Хотя эту задачу можно решать с помощью heavy-light декомпозиции, построив над каждым путём дерево отрезков для суммы (или просто предпосчитав частичные суммы, если в задаче отсутствуют запросы изменения), эта задача может быть решена более простыми техниками.

Если запросы модификации отсутствуют, то узнавать сумму на пути между двумя вершинами можно параллельно с поиском LCA двух вершин в алгоритме двоичного подъёма — для этого достаточно во время препроцессинга для LCA подсчитывать не только $2^k$ -ых предков каждой вершины, но и сумму чисел на пути до этого предка.

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

Оба этих способа дают относительно простые решения с асимптотикой $O (\log n)$ на один запрос.

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

Дано дерево, каждое ребро изначально покрашено в белый цвет. Поступают запросы вида $(a,b,c)$ , где $a$ и $b$ — номера вершин, $c$ — цвет, что означает, что все рёбра на пути из $a$ в $b$ надо перекрасить в цвет $c$ . Требуется после всех перекрашиваний сообщить, сколько в итоге получилось рёбер каждого цвета.

Решение — просто сделать дерево отрезков с покраской на отрезке над набором путей heavy-light декомпозиции.

Каждый запрос перекраски на пути $(a,b)$ превратится в два подзапроса $(a,l)$ и $(b,l)$ , где $l$ — наименьший общий предок вершин $a$ и $b$ (найденный, например, алгоритмом двоичного подъёма), а каждый из этих подзапросов — в $O (\log n)$ запросов к деревьям отрезков над путями.

Итого получается решение с асимптотикой $O (\log^2 n)$ на один запрос.

Задачи в online judges

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