luogu P2015 二叉苹果树 树形dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=210;
int f[N][N];
int e[N],ne[N],h[N],idx,w[N];
int n,m;
void add(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
void dfs(int u,int fa)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=e[i];
		if(v==fa)
			continue;
		dfs(v,u);
		for(int j=m;j>=1;j--)
			for(int k=0;k<=j-1;k++)
				f[u][j]=max(f[u][j],f[u][j-k-1]+w[i]+f[v][k]); 
	}
}
int main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1; i<n; i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	dfs(1,-1);
	cout<<f[1][m]<<endl;
	return 0;
}