Дерево + рюкзак: как набрать ровно k вершин из поддеревьев с максимальной ценностью (tree knapsack)?
Корневое дерево, у каждой вершины ценность val[v]. Можно выбрать вершину только если выбран её родитель (т.е. выбранное множество — связное поддерево, содержащее корень). Нужно выбрать ровно $k$ вершин с максимальной суммой ценностей. Это смесь дерева и рюкзака — как объединить?
2 ответа
Это tree knapsack: dp[v][j] = максимальная сумма ценностей, если в поддереве вершины v выбрано ровно j вершин (и сама v входит в выбор). Дети «склеиваются» как предметы рюкзака: объединяем поддеревья детей одно за другим, распределяя бюджет вершин.
int n, K;
vector<vector<int>> g;
vector<long long> val;
vector<vector<long long>> dp; // dp[v] размера sz[v]+1
vector<int> sz;
const long long NEG = -1e18;
void dfs(int v, int p) {
sz[v] = 1;
dp[v] = {0, val[v]}; // 0 вершин -> 0; 1 вершина (сама v) -> val[v]
for (int u : g[v]) if (u != p) {
dfs(u, v);
vector<long long> ndp(sz[v] + sz[u] + 1, NEG);
for (int a = 0; a <= sz[v]; ++a) if (dp[v][a] > NEG)
for (int b = 0; b <= sz[u]; ++b) if (dp[u][b] > NEG)
ndp[a + b] = max(ndp[a + b], dp[v][a] + dp[u][b]);
sz[v] += sz[u];
dp[v] = move(ndp);
}
}
// ответ dp[root][K]
Ключевой момент про сложность: если ограничивать вложенные циклы реальными размерами sz[v] и sz[u] (а не K), суммарно объединения дают $O(n^2)$ — известный результат «small-to-large по парам». Если же бюджет ограничен $K$, верхняя оценка $O(n \cdot K)$. Без ограничения размерами легко словить $O(n \cdot K^2)$ или хуже.
Самая частая ошибка тут — писать for (int a = 0; a <= K; ++a) вместо a <= sz[v]. С K корректность не страдает, но теряется та самая амортизация до $O(n^2)$: получится $O(nK^2)$. Доказательство $O(n^2)$ — каждая пара вершин $(x,y)$ «встречается» в перемножении ровно один раз (в их LCA), а пар $O(n^2)$.
Ещё нюанс: NEG-инициализация нужна, если требуется ровно $k$ (а не «не больше $k$»). Иначе недостижимые j дадут ложный 0 и испортят максимум.