MAXimal | |
добавлено: 6 Sep 2011 1:03 Содержание [скрыть] Heavy-light декомпозицияHeavy-light декомпозиция — это достаточно общий приём, который позволяет эффективно решать многие задачи, сводящиеся к запросам на дереве. Простейший пример задач такого вида — это следующая задача. Дано дерево, каждой вершине которого приписано какое-то число. Поступают запросы вида Описание алгоритмаИтак, пусть дано дерево Суть этой декомпозиции в том, чтобы разбить дерево на несколько путей таким образом, чтобы для любой вершины Понятно, что если мы научимся искать такую декомпозицию для любого дерева, это позволит свести любой запрос вида "узнать что-то на пути из Построение heavy-light декомпозицииПосчитаем для каждой вершины Далее, рассмотрим все рёбра, ведущие к сыновьям какой-либо вершины Все остальные рёбра назовём лёгкими. Очевидно, что из одной вершины Теперь построим саму декомпозицию дерева на непересекающиеся пути. Рассмотрим все вершины, из которых не выходит вниз ни одного тяжёлого ребра, и будем идти от каждой из них вверх, пока не дойдём до корня дерева или не пройдём лёгкое ребро. В результате мы получим несколько путей — покажем, что это и есть искомые пути heavy-light декомпозиции. Доказательство корректности алгоритмаВо-первых, заметим, что полученные алгоритмом пути будут непересекающимися. В самом деле, если бы два каких-то пути имели бы общее ребро, это бы означало, что из какой-то вершины исходит вниз два тяжёлых ребра, чего быть не может. Во-вторых, покажем, что спускаясь от корня дерева до произвольной вершины, мы сменим по пути не более Таким образом, мы не могли пройти более Следовательно, по пути от корня до любой вершины мы не можем сменить более Применения при решении задачПри решении задач иногда бывает удобнее рассматривать heavy-light как набор вершинно-непересекающихся путей (а не рёберо-непересекающихся). Для этого достаточно из каждого пути исключить последнее ребро, если оно являются лёгким ребром — тогда никакие свойства не нарушатся, но теперь каждая вершина будет принадлежать ровно одному пути. Ниже мы рассмотрим несколько типичных задач, которые можно решать с помощью heavy-light декомпозиции. Отдельно стоит обратить внимание на задачу сумма чисел на пути, поскольку это пример задачи, которая может быть решена и более простыми техниками. Максимальное число на пути между двумя вершинамиДано дерево, каждой вершине которого приписано какое-то число. Поступают запросы вида Построим заранее heavy-light декомпозицию. Над каждым получившимся путём построим дерево отрезков для максимума, что позволит искать вершину с максимальным приписанным числом в указанном сегменте указанного пути за Теперь, для того чтобы отвечать на поступивший запрос Аккуратно следует быть со случаем, когда, например, Таким образом, в процессе ответа на один подзапрос мы пройдём по Так мы получили решение за Если ещё дополнительно предпосчитать на каждом пути максимумы на всех суффиксах, то получится решение за Сумма чисел на пути между двумя вершинамиДано дерево, каждой вершине которого приписано какое-то число. Поступают запросы вида Хотя эту задачу можно решать с помощью heavy-light декомпозиции, построив над каждым путём дерево отрезков для суммы (или просто предпосчитав частичные суммы, если в задаче отсутствуют запросы изменения), эта задача может быть решена более простыми техниками. Если запросы модификации отсутствуют, то узнавать сумму на пути между двумя вершинами можно параллельно с поиском LCA двух вершин в алгоритме двоичного подъёма — для этого достаточно во время препроцессинга для LCA подсчитывать не только Есть и принципиально другой подход к этой задаче — рассмотреть эйлеров обход дерева, и построить дерево отрезков над ним. Этот алгоритм рассматривается в статье с решением похожей задачи. (А если запросы модификации отсутствуют — то достаточно обойтись предпосчётом частичных сумм, без дерева отрезков.) Оба этих способа дают относительно простые решения с асимптотикой Перекраска рёбер пути между двумя вершинамиДано дерево, каждое ребро изначально покрашено в белый цвет. Поступают запросы вида Решение — просто сделать дерево отрезков с покраской на отрезке над набором путей heavy-light декомпозиции. Каждый запрос перекраски на пути Итого получается решение с асимптотикой Задачи в online judgesСписок задач, которые можно решить, используя heavy-light декомпозицию:
|