樹上背包學習筆記

做完洛谷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;
}