HDU 1561 The more, The Better / 樹形DP

樹形DP 選m個節點權值加起來最大

因為可能是森林 就是都沒有限制就可以選 去一個超級源點0 這樣就是一棵樹了

然後就是基礎的樹形DP了 DP方程很好想 也很好轉移

#include 
#include 
#include 
using namespace std;
const int maxn = 210;
struct node
{
	int v, w;
};
vector  G[maxn];
int n, m;
int dp[maxn][maxn];
int a[maxn];
int sum[maxn];
void dfs(int u)
{
	sum[u] = 1;
	dp[u][1] = a[u];
	
	for(int i = 0; i < G[u].size(); i++)
	{
		node x = G[u][i];
		int v = x.v;
		dfs(v);
		sum[u] += sum[v];
		int mm = m;
		mm = min(m, sum[u]);
		for(int j = mm+1; j >= 1; j--)
		{
			for(int k = 0; k < j; k++)
			{
				dp[u][j] = max(dp[u][j], dp[u][j-k]+dp[v][k]);
			}
			//printf("%d\n", dp[u][j]);
		}
	}
}
int main()
{
	while(scanf("%d %d", &n, &m) && (n+m))
	{
		for(int i = 0; i <= n; i++)
			G[i].clear();
		for(int i = 1; i <= n; i++)
		{
			int u, v, w;
			scanf("%d %d", &u, &w);
			v = i;
			G[u].push_back((node){v, w});
			a[i] = w;
		}
		memset(dp, 0, sizeof(dp));
		memset(sum, 0, sizeof(sum));
		dfs(0);
		printf("%d\n", dp[0][m+1]);//+1是因為0也算進去了 
	}
	return 0;
}