Мне казалось, что этого нигде нет и я придумал что-то новое, но после того как я предложил задачу на codeforces, один из координаторов сказал, что пару лет назад уже видел задачу, где использовалось что-то похожее. Поэтому задачу отклонили. Так как я не смог придумать более интересную задачу на этот трюк, я просто напишу об этом в блоге.
Задача
Пусть дана какая-то задача, которую мы умеем решать с помощью центроидной декомпозиции. Например такая. Дано дерево, в каждой вершине записано число a[i]. Поступают 2 типа запросов.
Даны $$$v$$$, $$$d$$$, $$$c$$$. Надо перекрасить все вершины на расстоянии не больше $$$d$$$ от $$$v$$$ в цвет $$$c$$$.
Дана $$$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) будет выдавать новый центроид по следующему алгоритму:
Если в G есть цикл, то верни любую вершину на цикле.
Если 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 за перевод на английский язык.
