Переливания

Рассмотрим задачу, дано корневое дерево вершины которого раскрашенны в цвета. Для каждой вершины нужно посчитать количество различных цветов в её поддереве.

Что-бы узнать количество различных достаточно использовать std::set или std::unordered_set. Мы хотим для каждой вершины, в какой-то момент времени, получить такой set.

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

Оценим время работы

Рассмотрим вершину $v$. Пусть сейчас она находится в структуре, которая отвечает за $k$ вершин. Если мы посмотрели на вершину $v$, значит сейчас мы переливаем эту структуру в другую, следовательно, размер структуры, в которой находится $v$ хотя бы $2 * k$, следовательно, не может произойти больше $O(log(N))$ переливаний одной вершины, где $N$ - количество вершин во всем дереве. Тогда понятно, что всего переливаний будет $O(Nlog(N)$, и в зависимости от выбора set-а или unordered_set-а мы получим ассимптотику $- O(Nlog^2(N))$ или $O(Nlog(N))$.