Мне казалось, что этого нигде нет и я придумал что-то новое, но после того как я предложил задачу на 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$.↵
↵
Спасибо [user:andreyDagger,2023-01-26] за перевод на английский язык.
↵
Задача↵
------------------↵
Пусть дана какая-то задача, которую мы умеем решать с помощью центроидной декомпозиции. Например такая. Дано дерево, в каждой вершине записано число 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$.↵
↵
Спасибо [user:andreyDagger,2023-01-26] за перевод на английский язык.
