二叉苹果树

题目传送门

Description

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

2   5 
 \ / 
  3   4 
   \ / 
    1

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

Input

第1行2个数，N和Q(1<=Q<= N,1

Output

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

Sample Input

5 2
1 3 1
1 4 10
2 3 20
3 5 20

解题思路

我们观察到题目数据量不大,所以有两种选择：邻接矩阵和邻接表。因为邻接矩阵的代码简单，思路清晰，所以建议能写邻接矩阵的时候就不要写邻接表了。我们设ma[x][y]为边的值，因为树是双向的，所以要再记录ma[y][x]。
设tree[v,1]为节点v的左子树，tree[v,2]为节点v的右子树,然后我们再递归建树（因为树是递归定义的，所以很多时候建树都要考虑递归）。
建树的问题解决的了，我们就要列状态转移方程了。根据求什么设什么的原则，我们定义f[i][j]表示以i为节点的根保留k条边的最大值，那么f[v][k]=max(f[v][k],(f[tree[v][1]][i]+f[tree[v][2]][k-i-1]+num[v])),我们枚举i就可以了。正如我开头提到的。因为树是递归定义的所以我们可以用记忆化搜索的形式（dfs）来具体实现。而树本身严格分层，而且没有环。所以是不会重复的。
F[1][Q+1]就是答案。因为题目中给的是边的权值，而我们在处理时将每条边的权值全赋给其所连的父节点和子节点中的子节点（将关于边的问题转化为关于点的问题），所以最后是Q+1，表示点的数目

AC代码

#include<iostream>
#include<cstdio> 
using namespace std;
int n,q,b[105],a[105][105],f[105][105],tree[105][105];
void build(int x)//建图
{
   
	int o=0;//要在子程序int，不然会有问题
	for(int i=0;i<=n;i++)//枚举每一个点
	 if(a[x][i]!=-1)//如果相连
	 {
   
	 	o++;
	 	b[i]=a[x][i];//i的根为a[x][i]
	 	tree[x][o]=i;//树
	 	a[x][i]=a[i][x]=-1;//清零
	 	build(i);//递归
	 	if(o==2)return;//退出
	 }
}
void dfs(int x,int k)//搜索
{
   
    if(k==0)f[x][k]=0;//赋值
    else if(tree[x][1]==0&&tree[x][2]==0)f[x][k]=b[x];
    else
    {
   
        f[x][k]=0;
        for(int i=0;i<k;i++)//枚举k
        {
   
            if(f[tree[x][1]][i]==0)dfs(tree[x][1],i);//搜索
            if(f[tree[x][2]][k-i-1]==0)dfs(tree[x][2],k-i-1);
            f[x][k]=max(f[x][k],(f[tree[x][1]][i]+f[tree[x][2]][k-i-1]+b[x]));//状态转移
        }
    }
}
int main()
{
   
	scanf("%d%d",&n,&q);
	for(int i=0;i<=n;i++)//初值
	 for(int j=0;j<=n;j++)
	 	a[i][j]=a[j][i]=-1;
	for(int i=1;i<=n-1;i++)//输入
	{
   
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=a[y][x]=z;
	}
	build(1);//建
	dfs(1,q+1);//搜
	cout<<f[1][q+1];//输出
}

谢谢