二叉苹果树

https://www.luogu.com.cn/problem/P2015

设f[i][j]表示以i为根的子树中保留j个枝最多剩多少苹果

#include<bits/stdc++.h>
using namespace std;
int a[110][110],dp[110][110];
int n,q;
void dfs(int root,int fa)
{
	int x1=0,x2=0;
	for(int i=1;i<=n;i++)
	if(a[root][i]!=-1&&i!=fa) 
	{
		if(x1) x2=i;
		else x1=i;
		dfs(i,root);
	}
	for(int i=1;i<=q;i++)
	{
		dp[root][i]=max(dp[x1][i-1]+a[root][x1],dp[x2][i-1]+a[root][x2]);
		for(int j=0;j<=i-2;j++)//注意循环的边界，从只取左儿子到只取右儿子
		dp[root][i]=max(dp[root][i],dp[x1][j]+a[root][x1]+dp[x2][i-j-2]+a[root][x2]);
	}
}
int main()
{
	memset(a,-1,sizeof(a));//一个枝上的苹果个数可以为0，初始化成-1作为区分
	int x,y;
	cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		cin>>x>>y;
		cin>>a[x][y];
		a[y][x]=a[x][y];
	}
	dfs(1,0);
	cout<<dp[1][q];
	return 0;
}