苹果二叉树

题面描述

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）。这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树：

2 5

\ /

3 4

\ /

1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量，求出最多能留住多少苹果。

输入格式

第1行2个数，N和Q(1<=Q<= N,1<N<=100)。 N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。 每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。 每根树枝上的苹果不超过30000个。

输出格式

一个数，最多能留住的苹果的数量。

样例

数据范围

明显的树形DP，题意就是，选Q条边，使价值最大，但是从题意可以发现，这是一个苹果树，是现实当中的树（不是我的世界），所以可以很轻松的得出，选的边是还是一颗树，所以相当于是个最大生成树，而且必须根节点必须选。这仔细一想也很像背包问题，所以，我们就可以判断算法为背包类树形DP，然后就要干最重要的事了，那就是找到这个题的状态转移方程。

首先先定义一下状态，f[i][j]是以i为根节点，剩余j根树枝的时候苹果树的最大值。背包容量也就是Q。也就是开始遍历到所有根节点，然后在回溯的时候进行DP，以后还是要理解一下这个。

代码

#include<bits/stdc++.h>
using namespace std;
const int oi=2000010;
int ver[oi],head[oi],edge[oi],ne[oi],d1[oi],d[oi],s[oi],ans[oi],tot=0,sum=0,n,m;
int f[5000][5000];
void add(int x,int y,int z)
{
	ver[++tot]=y;
	edge[tot]=z;
	ne[tot]=head[x];
	head[x]=tot;
}
void dfs(int x,int y)
{
	for(int i=head[x];i;i=ne[i])
	{
		if(ver[i]==y)
		continue;
		dfs(ver[i],x);
		for(int j=m+1;j>=0;j--)
		{
			for(int k=j;k>=1;k--)
			{
				f[x][j]=max(f[x][j],f[x][j-k]+f[ver[i]][k-1]+edge[i]);
			}
		}
	}
}
int main()
{
	freopen("APPLE.in","r",stdin);
	freopen("APPLE.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z); 
	}
	dfs(1,0);
	cout<<f[1][m];
}