树上背包学习笔记
做完洛谷P2014实在心绪澎湃，感觉对树上背包有点感触所以分享一下心得
以洛谷P2014为例
我们设状态dp[u][j][m]为以u为根节点，只从前j个子树中选m个点的最大学分
那么这个问题就和01背包很像了，不过对于每个子树（每个物品）还要枚举它可能的不同学分（价值）
即在这个子树中选几个点
这么说更像是一个子树代表好几个物品
所以总的来说就是一个01背包了
那么就可以注意到滚动数组优化
第二维可以省略掉
状态转移方程：dp[u][j] = max(dp[u][j], dp[to[i]][k - 1] + v[i] + dp[u][j - k]);（k <- 1 to j）
j倒序枚举，k无所谓（物品出现先后顺序对问题无影响）
代码如下
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int h[N], to[N], v[N], ne[N], idx;
void add(int a, int b, int c) {to[++idx] = b;ne[idx] = h[a];h[a] = idx;v[idx] = c;
}
int dp[N][N];
void dfs(int u, int m) {if(m == 0) return;for(int i = h[u];i;i = ne[i]) {dfs(to[i], m - 1);for(int j = m;j;--j) {for(int k = j;k;--k) {dp[u][j] = max(dp[u][j], dp[to[i]][k - 1] + v[i] + dp[u][j - k]);}}}
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin>>n>>m;for(int i = 1;i <= n;++i) {int a, b;cin>>a>>b;add(a, i, b);}dfs(0, m);cout<<dp[0][m];return 0;
}