Centroid декомпозиция

Материал из Algocode wiki
Перейти к: навигация, поиск

Идея

Рассмотрим задачу: есть дерево на $10^5$ вершинах, требуется их раскрасить в 26 цветов (буквами латинского алфавита) так, чтобы для любой пары вершин на одного цвета на пути между ними была вершина с меньшим по номеру цветом. Для решения этой задачи введём следующее определение:

Определение:
Центроид —это вершина дерева, такая что у любого её поддерева размер $\le n / 2$.

Чтобы решить приведённую выше задачу, найдём центроид в дереве. Поставим туда букву «A». Любой путь из одного из поддеревьев этой вершины в другое будет проходить через «A». Осталось обработать случаи, когда и начало и конец пути лежат в одном поддереве центроида.

Рассмотрим каждое из поддеревьев. Найдём в них их центроиды. Будем называть их центроидами второго порядка у начального дерева. В каждый из центроидов второго порядка запишем «B». Рассмотрим поддеревья центроидов второго порядка. В ниих тоже есть центроиды. Назовём их центроидами третьего порядка. В каждый центроид тертьего порядка запишем «C». Аналогично у нас будут центроиды четвёртого порядка, в которые мы запишем «D» и т.д.

Замечаем, что поддеревья центроида $i$-го порядка имеют размер не более $\frac{n}{2^i}$. Тогда максимальный возможный порядок центроида — $\log_2 n$.

Замечаем, что любой путь, соединяющий какие-то 2 центроида $i$-го порядка проходит через центроид $i-1$го порядка. Так же любая вершина является центроидом какого-то порядка. Тогда задача решена.

Алгоритм построения

Массивы

$C[a]$ — порядок центроида вершины $a$

$P[n][i]$ — номер центроида $i$-го порядка, в поддереве которого лежит вершина $a$

Поиск центроида

Подвесим дерево за любую вершину. У центроида размер поддерева $\ge n/2$, так как иначе всё, что сверху имеет размер $> n / 2$.

Среди всех вершин, размер поддерева которых $\ge n/2$, возьмём вершину с минимальным размером поддерева. Если бы у какого-нибудь из её детей размер поддерева был бы $\ge n / 2$, то наша вершина не была бы минимальной среди таких. Тогда у всех её детей размер поддерева $\le n / 2$. Так как у этой вершины размер поддерева $\ge n / 2$, то у того, что сверху размер $\le n / 2$. Тогда эта вершина центроид.

Самый лёгкий способ найти её — запустится $dfs$-ом от любой вершины дерева, у каждой узнать размер поддерева. Далее спускаться из начальной вершины в ребёнка с максимальным размером до тех пор, пока его размер $\ge n/2$ (таких детей всегда не больше одного).

После этого находим центроид и запоминаем порядок вершины. После чего запускаемся $dfs$-ом от этой вершины и заполняем $P[a][0]$ для всех $a$.

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

Для упрощения кода можно объединить первой и второй $dfs$ на каждой итерации.

Реализация

int dfs(int v, int& c, int n, int p = -1) {
	int sz = 1;
	for (auto to : g[v]) {
		if (to != p && !used[to]) {
			sz += dfs(to, c, n, v);
		}
	}
	if (c == -1 && (n <= 2 * sz || p == -1)) {
		c = v;
	}
	return sz;
}

int centroid(int v, int n) {
	int c = -1;
	dfs(v, c, n);
	used[c] = 1;
	for (auto to : g[c]) {
		if (!used[to]) {
			ans[centroid(to, n / 2)] = c + 1;
		}
	}
	return c;
}

Задачи

  • Число путей длины $X$
  • Расстояние между вершинами в онлайне за $O(\log \log n)$ и $O(1)$
  • Минимум на пути за $O(\log \log n)$ и $O(1)$
  • Включить вершину и найти ближайшую включённую



Автор конспекта: Филипп Грибов

По всем вопросам пишите в telegram @grphil


Автор конспекта: Константин Амеличев (код)

По всем вопросам пишите в telegram @kik0s