树上背包
title: 树上背包
categories:
- ICPC
tags:
- null
abbrlink: 43d5793c
date: 2024-06-08 00:00:00
从树形dp到树上背包
1.https://www.luogu.com.cn/problem/P1122给定一棵树，每个点有点权，可能为负，求最大权值联通块。
Sol：我们考虑以1为根。树定向后对于任意一个连通块来说，他的形态也一定是一棵树，我们考虑在它的根上会计算到他对答案的贡献。所以问题转化为：求以i为根的最大子树权值和。
- 对于这个问题我们直接进行dp即可。dp[i]表示在i的子树里面，包含i的联通块的最大权值和。转移就是$dp[u]=a[u]+ \sum_{v \in son[u]} \max(0,dp[v])$
- 一个实现细节是：我们必须不能选择空集，所以我们需要保证我们的答案初始值足够小，是负无穷。
- 几乎一模一样的阅读理解题https://www.luogu.com.cn/problem/P5766
void solve() {
int n;
cin >> n;
vector<vector<int>> e(n + 1);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
int ans = -INT_MAX;
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
vector<int> dp(n + 1);
auto dfs = [&](auto self, int u, int fa) ->void{
dp[u] = a[u];
for (auto v : e[u]) {
if (v == fa)
continue;
self(self, v, u);
dp[u] += max(0, dp[v]);
}
ans = max(ans, dp[u]);
};
dfs(dfs, 1, 1);
cout << ans << endl;
}
上下界优化树形背包再谈树上背包的上下界优化 - Liuxizai’s Blog
以选课这个题为例题，体积为1的树形背包：我们直接做复杂度是$O(nm^2)$的
[P2014 CTSC1997] 选课 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
问题：给定一棵树，每个点有点权，找到大小为m的最大联通块，要求满足树形祖先依赖
Sol：考虑$dp[u][j]$表示u节点选了$j$体积的点，每次将一个儿子合并更新到$dp[u]$，具体转移是$dp[u][j]=\max_{k \le j,v \in son[u]}dp[v][k]+dp[u][j-k]$.考虑原地修改的话我们需要倒着枚举$j$,保证本轮的状态不被本轮前面状态更新。每次最后再把自己u这个节点的贡献更新进去，注意这里是必须更新的，而不是取max。
因为考虑u节点的话，我们就必须选择u节点。
- $j \ge weight[u] :dp[u][j]=dp[u][j-weight[u]]+value[u]$
- $j<weight[i]:dp[u][j]=0$
$O(nm^2)$Code：关于本题的实现细节有是一个森林，不利于我们直接dp。不然最后还要单独处理联通块之间的合并，考虑建立虚根，体积为0，价值为0。因此需要在最后合并当前节点的时候特判跳过u=1节点。
void solve() { int n, m; cin >> n >> m; int ans = 0; vector dp(n + 2, vector<int>(m + 1)); vector<vector<int>> e(n + 2); vector<int> val(n + 2); for (int i = 2; i <= n + 1; i++) { int fa; cin >> fa >> val[i]; if (fa == 0) e[1].push_back(i); else { fa++; e[fa].push_back(i); } } auto dfs = [&](auto self, int u) -> void { for (auto v : e[u]) { deb(u, v); self(self, v); for (int j = m; j >= 0; j--) { for (int k = 0; k <= j; k++) { dp[u][j] = max(dp[u][j], dp[v][k] + dp[u][j - k]); } } } if (u > 1) { for (int j = m; j >= 1; j--) dp[u][j] = dp[u][j - 1] + val[u]; dp[u][0] = 0; } }; dfs(dfs, 1); ans = *max_element(alls(dp[1])); cout << ans << endl; }需要倒序枚举 i 防止状态在转移前被覆盖。否则的话dp数组要多一维。
另一种处理虚根的方法，改变体积。由于可能是森林，所有没有直接先修课的节点，可以父亲视为节点 0，然后实际上就要选 m+1 个节点
发现可以进行背包枚举的上下界优化：每次合并子树背包的代价是$O(siz[u] \times siz[v])$。对于任意一对点，它们只会在$lca(u,v)$被合并计算贡献一次，所以这个问题的时间复杂度变成了$O(n^2)$
void solve() {
int n, m;
cin >> n >> m;
int ans = 0;
vector dp(n + 2, vector<int>(m + 1));
vector<vector<int>> e(n + 2);
vector<int> val(n + 2), sz(n + 2);
for (int i = 2; i <= n + 1; i++) {
int fa;
cin >> fa >> val[i];
if (fa == 0)
e[1].push_back(i);
else {
fa++;
e[fa].push_back(i);
}
}
auto dfs = [&](auto self, int u) -> void {
if (u > 1)
sz[u] = 1;
for (auto v : e[u]) {
deb(u, v);
self(self, v);
sz[u] += sz[v];
for (int j = min(sz[u], m); j >= 0; j--) {
for (int k = 0; k <= min(j, sz[v]); k++) {
dp[u][j] = max(dp[u][j], dp[v][k] + dp[u][j - k]);
}
}
}
if (u > 1) {
for (int j = min(m, sz[u]); j >= 1; j--) dp[u][j] = dp[u][j - 1] + val[u];
dp[u][0] = 0;
}
};
dfs(dfs, 1);
ans = *max_element(alls(dp[1]));
cout << ans << endl;
}
上面这份代码还能解决的问题是当n是$1e5$级别的时候，m是$1e3$,这样的话我们会发现体积这一维应该只需要算到$\min(m,sz[u])$。合并子树代价是$O(\min(sz[u],m)) \times O(\min(sz[v],m))$,可以证明这样的时间复杂度是$O(nm)$
图片为感性理解，以上两个时间复杂度的数学证明链接：树上背包的上下界优化 - ouuan的博客
总结： 1. 如果合并两个子树的代价等于树的大小的乘积的话，那么复杂度就是$O(n^2)$的
- 如果合并两个子树的代价等于子树大小和m取min的乘积的话，复杂度就是$O(nm)$的
- 如果不是这样，就没有相应的结论，比如合并的代价是$O((su + sv)^2) $
- 如果是距离相关的话，因为距离不会超过子树的大小，所以有类似的结论
第一阶段总结：们知道对于树上背包，若每个结点上只有总大小为 $O(1)$ 的物品，则总复杂度为 $O(n^2)$；若再限制背包大小为 m，则总复杂度为 $O(nm)$。
- 上面这种做法比较好写，而且还有一个优点，就是它事实上求出了每棵子树的 dp 值，换句话说，它可以统计到每个连通块的答案。当然，它也有一定的局限性，那就是第二维必须和子树的大小有关，否则复杂度就不对了。
- 这些实现无法解决多重背包，亦无法解决物品大小不为 1 的情况。此时，一个结点子树内的总物品数不再与子树大小同级，不适用之前的复杂度分析，由于在每个结点上我们都需要对儿子的背包进行非平凡的合并，总复杂度容易上升至 $O(nm^2)$。
- dfs 序优化的树上依赖性背包则避免了合并背包这一操作。
结论：节点体积为任意，背包限制是 m 的时间复杂度是 $O(Vm)$，V是$\sum abs(weight[i])$但其实际效果可能只有理论复杂度的$\frac{1}{20}$
dfs 序优化树上依赖性dfs 序优化树上依赖性背包学习笔记 - Liuxizai’s Blog
形式化的，树上依赖性背包指的是这样一类问题：若在某结点上选取了物品，则必须在其所有祖先上选取物品。
我们考虑直接在树的 dfs 序上进行 dp，在每个结点处我们都有两种决策：
- 选取至少一个物品，然后进入子树继续选取物品。
- 什么都不选，跳过当前子树。
具体问题构建：一棵树每个点有体积和价值，背包体积为M，n个点也就是n个物品，具有树形依赖。保证$n \times m \le6e7$
题外话：如何给这种输入的数据限制开二维dp的C_array,动态给指针分配内存
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> dp_pool; // 全局内存池
int **dp; // DP数组指针
int n, m; // n: 行数, m: 列数
// 函数：动态分配内存
void allocate_dp_array(int n, int m) {
dp_pool.resize(n * m); // 分配一维内存池
dp = new int *[n]; // 分配指针数组
for (int i = 0; i < n; ++i) {
dp[i] = dp_pool.data() + i * m; // 每个指针指向内存池中相应的起始位置
}
}
// 示例：清理分配的内存
void deallocate_dp_array() {
delete[] dp; // 释放指针数组
dp = nullptr; // 设置为nullptr以避免悬挂指针
}
int main() {
n = 5; // 例如，5行
m = 10; // 例如，10列
allocate_dp_array(n, m);
// 示例使用：初始化DP数组
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
dp[i][j] = i + j; // 填充示例数据
}
}
// 打印结果
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << dp[i][j] << " ";
}
cout << endl;
}
deallocate_dp_array(); // 释放内存
return 0;
}
同样代码可以解决的题：每个点都有权值和重量，求一个重量恰好为k的包含根的连通块，最大的权值和
Sol:考虑按dfs序做，$r[u]+1$表示序列中跳过x的子树的下一个位置，$dp[i][j]$表示dfs序中 [i, n+1] 这一段的节点重量等于j的最大权值。转移：$dp[i][j]=\max(dp[r[i]+1][j],dp[i+1][j-wei[id[i]]]+val[id[i]])$
如果不选第i个节点，则直接跳过i整个子树，从r[i]+1转移过来
选第$i$个的节点的前提是$j>=wei[u]$，$id[i]$表示dfs序为i的节点在树上的真实编号，从i+1转移过来。
void solve() {
int n, m;
cin >> n >> m;
// dfn:useful(1-n+1),init(n+2=-inf),(0_space);
vector dp(n + 3, vector<int>(m + 1));
for (int i = 1; i <= m; i++)
dp[n + 2][m] = -inf;
vector<vector<int>> e(n + 1);
for (int i = 1; i <= n; i++) {
int fa;
cin >> fa;
e[fa].push_back(i);
}
vector<int> wei(n + 1), val(n + 1);
for (int i = 1; i <= n; i++)
cin >> wei[i];
for (int i = 1; i <= n; i++)
cin >> val[i];
vector<int> l(n + 1), r(n + 1), id(n + 2);
int idx = 0;
auto dfs = [&](auto self, int u) -> void {
l[u] = ++idx;
id[idx] = u;
for (auto v : e[u]) {
self(self, v);
}
r[u] = idx;
};
dfs(dfs, 0);
for (int i = n + 1; i >= 1; i--) {
int u = id[i];
for (int j = 0; j <= m; j++) {
if (j >= wei[u])
dp[i][j] = max(dp[i][j], dp[i + 1][j - wei[u]] + val[u]);
dp[i][j] = max(dp[i][j], dp[r[u] + 1][j]);
}
}
cout << dp[1][m] << endl;
}
多叉树变二叉树，泛化物品222222222222222[笔记]树形dp - 2/4（树上背包类） - Sinktank - 博客园 (cnblogs.com)
分块续4444444444444PermuTree (hard version) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
44444444444444ICPC2023济南站题解（A B D E G I K M） - maple276 - 博客园 (cnblogs.com)
PermuTree (easy version) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
分块续444444444444The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan) - 空気力学の詩 - 博客园 (cnblogs.com)
练习1：在树上找一个连通块，满足任意两点之间的距离都不超过d,使得权值之和最大，权值可能是负数
Sol:$ f[i][j]$:表示i这个子树里面，选择一个包括i的连通块，并且这个联通块中距离i这个点最远距离是j 那么合并子树的联通块的时候，对于$f[v1][j1]，f[v2][j2]$两个子树,他们需要满足$j1+j2+2<=d$并且将结果更新到$ f[u][max(j1, j2)+1]$里面去
练习2：在树上找一个点集，满足任意两点之间的距不小于d，使得权值之和最大，权值可能是负数
Sol:$f[i][j]：$表示在i个子树里面选一个点集，并且这个点集里面的点距离i的最小距离是j，当然如果j==0就表示选了i这个
点, 那么合并子树的时候，$f[v1][j1],f[v2][j2]$, 需要满足$j1+j2+2>=d$并且将结果更新到$f[u][min(j1, j2)+1]$当中
3.题意:给定一棵n个节点的树,求留下一棵m个结点的子树，最少需要切断几条边?https://www.luogu.com.cn/problem/U53878
Sol：首先可以有这么一个想法：设$ f[u][s]$ 表示在节点 u ，获得大小为s的子树所需要删除的边的个数。
最后计算答案的时候应该注意$dp[u][m]$强制选择了u节点，但答案不一定选u节点，所以考虑$ans=\min_{u \in[1,n]}{dp[u][m]}$.进一步修正，考虑如果一个非根节点u像作为最终答案还需要砍掉u和$fa[u]$那条边，$ans=\min(dp[1][m],dp[u][m](u \in [2,n]))$
void solve() {
int n, m;
cin >> n >> m;
vector dp(n + 1, vector<int>(m + 1, inf));
vector<vector<int>> e(n + 1);
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
}
vector<int> sz(n + 1);
// 强制选u，且以u为根的子树中包含j个点，所需要删边最小数目
auto dfs = [&](auto self, int u) -> void {
dp[u][1] = 0; // 初始的时候考虑没有子树
sz[u] = 1;
for (auto v : e[u]) {
deb(u, v);
self(self, v);
sz[u] += sz[v];
for (int j = min(m, sz[u]); j >= 1; j--) {
dp[u][j] += 1; // k=0不分配体积给v，需要删1条边
for (int k = 1; k <= min(sz[v], j - 1); k++) {
dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k]);
}
}
}
};
dfs(dfs, 1);
int ans = dp[1][m];
for (int i = 2; i <= n; i++) ans = min(ans, dp[i][m] + 1);
cout << ans << endl;
}
4.https://www.luogu.com.cn/problem/P1273给定一棵树，边有边权，叶子节点有点权。选择一个连通块，满足树上依赖关系(也就是选了u点，u到根的点都必须选),最大化这个联通块的价值。
- 价值定义为联通块中$所有叶子的点权-所有边的边权$
Sol: 设$f[i][j]$表示以i为根的子树内选出j个叶子节点的最大权值和.考虑枚举子节点选了k个叶子节点
- $k=0$ $dp[u][j]->dp[u][j]+dp[v][k]$,又因为$dp[v][k]=0$,所以相当于没更新
- k>0 $dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-w)$，说明必须连u和v这条边，也就是必须付出w的代价。
- 可以维护sz[u]表示u的子树中叶子节点的数量，从而进行上下界优化。
struct edge {
int v, w;
};
void solve() {
int n, m;
cin >> n >> m;
vector<vector<edge>> e(n + 1);
vector<int> val(n + 1);
vector dp(n + 1, vector<int>(m + 1, -inf));
for (int i = 1; i <= n - m; i++) {
int num;
cin >> num;
for (int j = 1; j <= num; j++) {
int v, cost;
cin >> v >> cost;
e[i].push_back({v, cost});
}
}
vector<int> sz(n + 1);
for (int i = n - m + 1; i <= n; i++) cin >> val[i];
auto dfs = [&](auto self, int u) -> void {
dp[u][0] = 0; // 这里初始化很重要
if (u >= n - m + 1) {
sz[u] = 1;
dp[u][1] = val[u]; // 这个只能对叶子做，非叶子要保持-inf
}
for (auto [v, w] : e[u]) {
self(self, v);
sz[u] += sz[v];
for (int j = min(m, sz[u]); j >= 1; j--) { // 至少选一个
for (int k = 1; k <= min(j, sz[v]); k++) { // 可以全给当前这个，不是依赖
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k] - w);
// 写出k=0式子发现相当于没更新，感性理解
// 新子树一个都不选当然无法更新当前根节点的dp值
}
}
}
};
dfs(dfs, 1);
int ans = 0;
for (int i = 1; i <= sz[1]; i++) {
if (dp[1][i] >= 0) {
ans = i;
}
}
cout << ans << endl;
}