Центроидная декомпозиция на графе с циклами

Правка ru5, от dimss, 2023-01-26 15:38:12

Мне казалось, что этого нигде нет и я придумал что-то новое, но после того как я предложил задачу на codeforces, один из координаторов сказал, что пару лет назад уже видел задачу, где использовалось что-то похожее. Поэтому задачу отклонили. Так как я не смог придумать более интересную задачу на этот трюк, я просто напишу об этом в блоге.

Задача

Пусть дана какая-то задача, которую мы умеем решать с помощью центроидной декомпозиции. Например такая. Дано дерево, в каждой вершине записано число a[i]. Поступают 2 типа запросов.

  1. Даны $$$v$$$, $$$d$$$, $$$c$$$. Надо перекрасить все вершины на расстоянии не больше $$$d$$$ от $$$v$$$ в цвет $$$c$$$.

  2. Дана $$$v$$$. Надо узнать цвет вершины $$$v$$$.

Теперь эта задача не на дереве, а на связном графе. Но есть одно очень интересное ограничение. m — n + 1 $$$\le$$$ 100. То есть в дерево добавили не больше 100 рёбер.

Сначала напомню как решалась задача на дереве. Мы строили дерево центроидов глубины $$$O(\log n)$$$, для каждого центроида хранили структуру, которая умела красить вершины от $$$C$$$ на расстоянии не более $$$d$$$ и узнавать цвет вершины. Эта структура называется стек, в котором хранятся тройки элементов (расстояние, цвет, время). При чем расстояние строго убывает. Тогда при покраске надо удалить некоторые элементы с конца стека и положить новый элемент. А при запросе цвета ответ можно найти бинпоиском по локальной глубине $$$v$$$.

Мы научились отвечать на запросы, если красим вершины от заданного центроида. Теперь переберем все центроиды $$$C$$$, которые являются предками $$$v$$$ в дереве центроидов и для них сделаем операции выше. Если запрос первого типа, и мы красим от $$$v$$$ на расстояние не более $$$d$$$, то от $$$C$$$ надо покрасить на расстояние не более $$$d - dist(v, C)$$$ Если мы сейчас отвечаем на запрос второго типа, то из всех цветов надо выбрать тот, у которого максимальное время. Почему это работает? Предположим, что был запрос покраски от $$$v$$$, который задел $$$u$$$, цвет которой мы хотим сейчас узнать. Тогда существует центроид $$$C = lca(v, u)$$$ в дереве центроидов. $$$C$$$ — общих центроид и для $$$v$$$, и для $$$u$$$. Причем, он находится на пути от $$$v$$$ до $$$u$$$ в исходном дереве. Тогда когда мы переберем $$$C$$$, правильный ответ нам гарантирован.

Но теперь, когда не дерево, а граф, то построить дерево центроидов нельзя. Давайте переделаем определение центроида и построим нечто похожее. get(G) будет выдавать новый центроид по следующему алгоритму:

  1. Если в G есть цикл, то верни любую вершину на цикле.

  2. Если G — дерево, то верни любой обычный центроид.

Еще одно изменение в постройке — это то, что теперь глубины вершин надо искать не dfs-ом, а bfs-ом. Тогда дерево новых центроидов будет выглядеть как бамбук из 100 вершин, к которому подвешено дерево обычных центроидов. Я утверждаю, что тогда алгоритм выше будет корректно работать. Опять же, пусть была покраска в $$$v$$$, которая задевает $$$u$$$ и мы хотим узнать цвет $$$u$$$. Тогда существует вершина $$$C$$$, которая является предком $$$lca(v, u)$$$ (обратите внимание, что не ровно lca, а предком lca), что крайчайший путь из $$$v$$$ в $$$u$$$ проходит через вершину $$$C$$$. И когда мы ее переберем, посчитается правильный ответ.

Обработка первого запроса амортизировано занимает $$$O(m - n + 1 + \log n)$$$, а второго $$$O((m - n + 1 + \log n) \log n)$$$.

Другие задачи

Все задачи, который я знаю и умею решать, где используются центроиды для ответа на запросы (таких не очень много), я умею обобщать на граф. Но, к сожалению, не любую задачу на дереве можно так обобщить. Например, если центроиды используются для подсчета количества путей в дереве (более точно, количество пар $$$v$$$, $$$u$$$), то здесь некоторые пути будут учитываться несколько раз, если между ними несколько крайчайших путей. Ответ, полученный таким способом дает неплохую верхнюю границу. Реальный ответ меньше не больше чем на $$$(m - n + 1)n$$$.

Спасибо andreyDagger за перевод на английский язык.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский dimss 2023-01-26 15:41:17 4
en5 Английский dimss 2023-01-26 15:40:16 78
en4 Английский dimss 2023-01-26 15:39:27 0 (published)
ru5 Русский dimss 2023-01-26 15:38:12 0 (опубликовано)
en3 Английский dimss 2023-01-26 15:37:35 73
ru4 Русский dimss 2023-01-26 15:37:00 73
en2 Английский dimss 2023-01-26 15:35:34 140
en1 Английский dimss 2023-01-26 15:34:26 4147 Initial revision for English translation (saved to drafts)
ru3 Русский dimss 2023-01-26 12:03:12 5 Мелкая правка: 'дел задачу использов' -> 'дел задачу, где использов'
ru2 Русский dimss 2023-01-26 11:57:44 3840 Мелкая правка: 'm - n + 1 ≤≤\leq 100. То е' -> 'm - n + 1 $$$\le$$$ 100. То е'
ru1 Русский dimss 2023-01-26 10:52:14 54 Первая редакция (сохранено в черновиках)