Центроид дерева: как найти вершину, у которой максимальное поддерево минимально?
Что такое центроид дерева и чем он отличается от центра? Нужно найти центроид — вершину, при удалении которой все компоненты имеют размер ≤ n/2. Как его найти за один проход и почему он всегда существует (и их может быть максимум два)?
2 ответа
Центроид — вершина, удаление которой разбивает дерево на компоненты, каждая размером ≤ ⌊n/2⌋. Он всегда существует, и их не больше двух (если два — они соседи).
Не путать с центром дерева: центр — вершина (или две), минимизирующая эксцентриситет (макс. расстояние до других); это середина диаметра. Центроид — про размеры поддеревьев, центр — про расстояния. Это разные вещи.
Поиск центроида: считаем размеры поддеревьев sz[v] одним DFS. Вершина v — центроид, если для всех её детей sz[child] <= n/2 И «верхняя» часть n - sz[v] <= n/2.
int n; vector<int> g[N]; int sz[N];
void calcSize(int v, int p) {
sz[v] = 1;
for (int u : g[v]) if (u != p) { calcSize(u, v); sz[v] += sz[u]; }
}
int findCentroid(int v, int p) {
for (int u : g[v]) if (u != p)
if (sz[u] > n / 2) return findCentroid(u, v); // идём в тяжёлого ребёнка
return v;
}
// calcSize(root, -1); int c = findCentroid(root, -1);
Почему работает спуск: если у вершины есть ребёнок с поддеревом > n/2, центроид лежит в нём — идём туда. Когда такого ребёнка нет, эта вершина и есть центроид (тогда и верхняя часть ≤ n/2 автоматически).
Сложность O(V), память O(V). Существование: спуск всегда останавливается, т.к. размер «тяжёлой» части строго убывает.
Зачем это нужно — центроидная декомпозиция. Идея: находим центроид, «обрабатываем» пути, проходящие через него, удаляем его, рекурсивно повторяем для каждой образовавшейся компоненты. Поскольку каждый раз отрезается ≥ половина, глубина рекурсии O(log V), и суммарно вершина участвует в O(log V) уровнях.
Это даёт решения задач вида «посчитать число пар вершин с расстоянием = k» за O(V log V) или O(V log² V). Каждый путь в дереве проходит через центроид ровно одного уровня декомпозиции — это и есть инвариант, на котором всё держится. Реализация требует аккуратного пересчёта размеров после каждого удаления центроида (помечаем удалённые и не заходим в них).