Дерево-рюкзак

Задача: дано дерево и число $p$. Удалить минимальное число рёбер так, чтобы хотя бы одна из образовавшихся компонент имела размер ровно $p$.

Слово «ровно» убивает жадность — это тот же признак, по которому рюкзак не решается жадно. Значит, размер входит в состояние.

$dp[v][k]$ — минимальное число удалённых рёбер в поддереве $v$ при условии, что компонента, содержащая $v$, имеет размер ровно $k$.

Пересчёт

Детей добавляем по одному, каждый раз строя новый слой из старого. Для очередного ребёнка $u$ есть два варианта.

Ребро оставляем. Тогда к нашей компоненте приклеивается компонента $u$ размера $b$:

$$dp'[v][a+b] = \min\bigl(dp'[v][a+b],\ dp[v][a] + dp[u][b]\bigr)$$

Ребро удаляем. Тогда всё поддерево $u$ отваливается, а мы платим одно ребро:

$$dp'[v][a] = \min\bigl(dp'[v][a],\ dp[v][a] + 1\bigr)$$

void dfs(int v, int p) {
    sz[v] = 1;
    dp[v].assign(2, INF);
    dp[v][1] = 0;                                  // пока только сама вершина
    for (int u : g[v]) if (u != p) {
        dfs(u, v);
        vector<int> nd(sz[v] + sz[u] + 1, INF);
        for (int a = 1; a <= sz[v]; a++) {         // границы — вот это важно
            if (dp[v][a] >= INF) continue;
            nd[a] = min(nd[a], dp[v][a] + 1);      // ребро вырезаем
            for (int b = 1; b <= sz[u]; b++)
                if (dp[u][b] < INF)
                    nd[a + b] = min(nd[a + b], dp[v][a] + dp[u][b]);
        }
        sz[v] += sz[u];
        dp[v] = nd;
    }
}

Ответ — минимум по всем вершинам $v$ величины $dp[v][p]$ плюс единица за отрезание $v$ от родителя (для корня — плюс ноль). Перебор по всем $v$ нужен потому, что нужная компонента может висеть где угодно; её самая высокая вершина и будет тем $v$, которое мы переберём.

Проверено: на 30 000 деревьев до девяти вершин совпало с перебором всех подмножеств удаляемых рёбер.

Асимптотика: не куб, а квадрат

На первый взгляд получается $O(n^3)$: перебираем ребро, потом $a$, потом $b$.

Первое уточнение очевидно: вершин с их детьми не $n \cdot n$, а $n-1$ ребро суммарно. Остаётся $O(n^3)$: ребро, $a$, $b$.

Но если писать границы честно — $a$ до текущего размера уже собранной части, $b$ до размера поддерева $u$, — получается $O(n^2)$.

Доказательство красивое. Перебор $a$ — это выбор одной вершины из уже собранной части. Перебор $b$ — выбор одной вершины из поддерева нового ребёнка. Значит, время работы равно числу рассмотренных пар вершин $(s, t)$.

Каждая пара рассматривается ровно один раз: на уровне их наименьшего общего предка. Именно там $s$ и $t$ впервые оказываются в разных объединяемых частях. Пар всего $\binom{n}{2}$ — отсюда квадрат.

Проверка

Измерено число выполнений внутренней строки:

$n$	бамбук	звезда	случайное дерево	$n(n-1)/2$
100	4 950	4 950	4 950	4 950
300	44 850	44 850	44 850	44 850
1 000	499 500	499 500	499 500	499 500
3 000	4 498 500	4 498 500	4 498 500	4 498 500

Не «примерно квадрат», а ровно $\binom{n}{2}$, и одинаково на любой форме дерева. Ровно то, что обещает рассуждение про пары.

Что будет, если написать границы небрежно

Если перебирать for (a = 1; a <= n; a++) и for (b = 1; b <= n; b++) вместо sz[v] и sz[u], ответ останется верным, а работа станет кубической. На $n = 3000$ это разница между 4,5 миллиона операций и 27 миллиардами.

Это тот редкий случай, когда асимптотика зависит не от алгоритма, а от аккуратности записи цикла.

Тот же приём в других задачах

Схема «состояние — вершина и количество, слияние детей по одному» решает целый класс:

• выбрать ровно $k$ вершин поддерева с максимальной суммой весов;
• разбить дерево на компоненты размера не больше $k$, минимизируя число разрезов;
• посчитать число способов покрасить дерево так, чтобы чёрных вершин было ровно $k$.

Во всех случаях оценка та же: $O(n^2)$ при честных границах.