【树形DP】洛谷 P2014 选课

题链

$dp[u][j]$表示$u$这个节点取$j$个物品的最大值（包含$u$点）；

设$v$是$u$的一个子节点，并且递归求解出$dp[v][j]$，递归终点就是$dp[v][1] = val[v]$（$val[v]$ 表示点$v$的权值），然后合并$u$，$v$；

答案就是$dp[0][m+1]$，从$0$号点选取$m+1$个物品的最大值（$0$号物品$val[0] = 0$）；

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 998244353
#define MAXN 1e18
#define MS 309

int n,m;
vector<int > vc[MS];
int val[MS];
int dp[MS][MS];
int sz[MS];

void dfs(int u,int fa){
	dp[u][1] = val[u];
	sz[u] = 1;
	for(auto &v:vc[u]){
		if(v == fa) continue;
		dfs(v,u);
		sz[u] += sz[v];
		for(int i=sz[u];i>=2;i--){
			for(int j=0;j<=sz[v];j++){
				if(i-j>=1) dp[u][i] = max(dp[u][i] , dp[u][i-j]+dp[v][j]);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		int x,w;
		cin >> x >> w;
		vc[x].push_back(i);
		val[i] = w;
	}
	dfs(0,-1);
	cout << dp[0][m+1] << "\n";
	
	return 0;
}