P2015 二叉苹果树

题目链接

题意：
给一棵树，每个边都有权值，选择一些边删除，剩余m条边。问删除后所有变得权值和最大是多少？
树形dp 01背包问题；
dp数组：dp[maxn][maxn] ；
dp[x][i] 代表x为根节点的子树上有i条边的最大权值；
转移方程：
num[x]为子树上目前有多少边，为什么说目前呢？ 因为子节点还没遍历完，

for (int j = min(m,num[x]); j > 0; j -- )
		for (int k = 0; k <= min(j - 1,num[v]); k ++ )
			dp[x][j] = max(dp[x][j],dp[v][k] + dp[x][j - k - 1] + t.second);

因为如果最后剩余的有v这个子树上的边的话，那么x节点与v节点之间的边肯定不能删，所以就是j-k-1；然后再加上这条边。
我还是想不到dp数组能代表点啥。还是菜了；
上代码:

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
typedef pair<int,int> PII;
const int maxn = 105;
vector<PII> vv[maxn];
int dp[maxn][maxn];//dp[x][i] 表示x的字数上保留i条边得到的权值最大值 
int num[maxn];
int m;
void dfs(int x,int f)
{
   
	num[x] = 0;
	for (int i = 0; i < vv[x].size(); i ++ )
	{
   
		PII t = vv[x][i];
		if(t.first == f)
			continue;
		dfs(t.first,x);
		int v = t.first;
		num[x] += num[v] + 1;
		for (int j = min(m,num[x]); j > 0; j -- )
		{
   
			for (int k = 0; k <= min(j - 1,num[v]); k ++ )
			{
   
				dp[x][j] = max(dp[x][j],dp[v][k] + dp[x][j - k - 1] + t.second);
			}
// printf("%d ",dp[x][j]);
		}
// printf("\n");
	}
// printf("\n %d %d \n",m,x);
}


int main()
{
   
	int n;
	scanf("%d%d",&n,&m);
	for (int i = 1; i < n; i ++ )
	{
   
		int x,y,val;
		scanf("%d%d%d",&x,&y,&val);
		vv[x].push_back(make_pair(y,val));
		vv[y].push_back(make_pair(x,val));
	}
	dfs(1,0);
	printf("%d\n",dp[1][m]);
 }