centroid.md

Центроидная декомпозиция

Центроидная декомпозиция — обобщение метода «разделяй-и-властвуй» на деревья. Обычно её используют для решения двух типов задач: «сколько есть путей с такими-то свойствами» и «есть ли такое-то свойство у этого пути».

Иногда вместо неё можно написать heavy-light декомпозицию, что чуть сложнее, или метод переливаний, что чуть проще.

Определение. Центром или центроидом (англ. centroid) дерева будем называть вершину, при удалении которой размеры оставшихся компонент будут не более $\frac{n}{2}$.

Центроид всегда существует — это следует из алгоритма его поиска:

int s[maxn];

int sizes (int v) {
    s[v] = 1;
    for (int u : g[v])
        // для простоты считаем, что дерево корневое
        s[v] += sizes(u);
    return s[v];
}

// второй параметр -- размер дерева
int centroid (int v, int n) {
    for (int u : g[v])
        if (s[u] > n/2)
            return centroid(u, n);
    return v;
}

Утверждение. centroid действительно находит цетроид.

Доказательство:

• centroid вернет вершину, у которой размеры всех детей не больше $\frac{n}{2}$ (это явно проверяется в if-е).
• Мы пришли в эту вершину, когда её размер был больше $\frac{n}{2}$, а это значит, что в «обратном» направлении есть не более $n - (\frac{n}{2}+1) = \frac{n}{2}-1$ вершин.
• Значит, размеры всех соседей не больше половины $n$, и алгоритм корректен.

Иногда центроидов два (пример: 1-2-3-4), и тогда алгоритм вернёт «нижний» центроид.

Определение. Центроидной декомпозицией будем называть рекурсивный процесс «выделить центроид, удалить, запуститься от компонент».

Определение. Компонентой центроида будем называть множество вершин, достижимых из центроида непосредственно перед его удалением.

Заметим, что в конце всё дерево будет удалено, а значит каждая вершина ровно один раз побывала центроидом своей компоненты.

Теперь поймём, зачем мы всё это делали.

Утверждение. Каждая вершина входит в $O(\log n)$ компонент.

Доказательство. Центроид разбивает дерево на компоненты в хотя бы два раза меньшего размера. Значит, никакая вершина не может «прожить» более $\lceil \log_2 n \rceil$ разделений.

Следствие. Центроидная декомпозиция (см. определение выше) работает за $O(n \log n)$.

Утверждение. Для любого пути $a \leadsto b$ есть единственный центроид $c$, в чьей компоненте были и $a$, и $b$.

Доказательство. Каждая вершина когда-то была центроидом. Какая-то из вершин на пути была центроидом первой, и она навсегда разъединила $a$ и $b$.

Это очень важные выводы. Получается, что в процессе центроидной декомпозиции и для каждого простого пути будет ровно одна ситуация, когда этот путь содержится в какой-то компоненте и проходит через центроид. Ровно в этот момент мы можем обработать какой-то запрос, пользуясь техникой, похожей на метод переливаний.

Подсчет путей с заданным свойством

Рассмотрим конкретный пример: подсчёт путей заданной длины.

Вмешаемся в процесс центроиднодной декомпозиции: для каждого центроида перед его удалением будем прибавлять к ответу число интересующих нас путей, которые проходят через этот центроид.

Количество таких путей можно посчитать за размер текущей компоненты: заведём массив d, в котором будем хранить количество вершин на каждом расстоянии от 0 до размера компоненты. Подвесим наше дерево-компоненту за центроид и будем запускать от его непосредственных детей dfs, который будет возвращать временный массив t — список глубин вершин в этом поддереве. Мы можем пройтись по каждому значению x в нём и добавить к ответу d[l-x], а затем добавить все значения из t в d. Можно убедиться, что таким образом каждый интересующий нас путь будет учтён ровно один раз.

int l = 179; // нужная нам длина
int ans = 0;

// нам лень явно удалять вершины: заведем массив used -- была ли вершина удалена
bool used[maxn];
int s[maxn]; // размеры поддеревьев

void sizes (int v, int p) {
    s[v] = 1;
    for (int u : g[v])
        if (u != p && !used[u])
            sizes(u, v), s[v] += s[u];
}

int centroid (int v, int p, int n) {
    for (int u : g[v])
        if (u != p && !used[u] && s[u] > n/2)
            return centroid(u, v, n);
    return v;
}

// записывает в t[] глубины вершин
void dfs (int v, int p, int d, vector<int> &t) {
    t.push_back(d);
    for (int u : g[v])
        if (u != p && !used[u])
            dfs(u, v, d + 1, t);
} 

void solve (int v) {
    /* <единственный зависящий от конкретной задачи код> */
    sizes(v);
    vector<int> d(s[v], 0);
    d[0] = 1;
    for (int u : g[v]) {
        if (!used[u]) {
            vector<int> t;
            dfs(u, v, 1, t);
            for (int x : t)
                if (x <= l)
                    ans += d[l-x];
            for (int x : t)
                d[x]++;
        }
    }
    /* </единственный зависящий от конкретной задачи код> */

    used[v] = 1;
    for (int u : g[v])
        if (!used[u])
            solve(centroid(u, v, s[u]));
}

Асимптотика $O(n \log n)$, потому что на каждую из $O(n)$ вершин мы потратим $O(1)$ операций на каждом из $O(\log n)$ «уровней» центроидной декомпозиции.

Запросы на путях — offline

Мы находим всё, что нам надо, сразу после того, как получили новую компоненту. Если у нас есть список запросов «посчитать что-то на пути», то мы часто можем обработать их в offline.

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

Например, при запросах суммы на пути, мы можем насчитать во внутреннем dfs для каждой вершины сумму на пути от её текущего центроида, и если при обработке текущей компоненты встретим вторую вершину запроса, в какой-то другой ветке, то просто возьмем её сумму и уже посчитанной суммой на пути до первой вершины.

Таким образом, каждый запрос будет просмотрен $O(\log n)$ раз, пока не будет удален, и асимптотика составит $O(q \log n + n \log n)$.

Запросы на путях — online

Альтернативно, можно сначала «построить» центроидную декомпозицию, а потом отвечать на запросы.

Пусть мы хотим посчитать отвечать на запросы минимума на путях и не знаем, как решать LCA двоичными подъемами. Создадим двумерный массив centroid[][] размера $n \times \log n$, в котором для каждой вершины будем хранить $O(\log n)$ центроидов, в чьи компоненты она когда-то входила. Помимо этого, в таком же массиве будем хранить информацию, которая нам будем нужна для ответа на запросы — в данном случае для каждой пары вершина-центроид будем хранить минимум на соответствующем пути.

Тогда, при ответе на запрос, мы за $O(\log n)$ или даже $O(\log \log n)$ операций находим центроид на нужном нам пути (первые сколько-то значений centroid[v] и centroid[u] будут совпадать — нас интересует последнее) и берём в качестве ответа минимум от минимумов на двух путях до центроида.

Асимптотика при более долгих пересчётах

Представим, что мы написали «мердж» (ту часть, которая отвечает за ответ на запросы или подсчёт путей, идущих через центроид) не за линейное время, а за $O(n \log n)$, например, где-то использовав set. Сильно ли это хуже по времени?

В худшем случае (в бамбуке) каждый раз компонента будет разбиваться на две равные части. Просуммируем общее количество операций в дереве рекурсии (см. мастер-теорему):

$$ \sum_{k=0}^{\log n} n \log \frac{n}{2^k} = \sum_{k=0}^{\log n} n (\log n - k) = n \sum_{k=0}^{\log n} k = \Theta (n \log^2 n) $$

Мораль: используйте хэш-таблицы.