记忆化搜索版

#include<bits/stdc++.h>
using namespace std;
const int N=105,INF=0x3fffffff;
int n,q;
struct edge
{
	int v,w;
};
vector<edge>g[N];
int size[N];//i点子树树枝的数量 
int f[N][N];//只保留j条树枝,i能留的最大苹果数 
void dfs_init(int u,int fa)
{
	for(auto v:g[u])
	{
		if(v.v==fa)continue;
		dfs_init(v.v,u);
		size[u]+=size[v.v]+1;
	}
}
int dfs(int u,int k,int fa)
{
	k--;
	if(f[u][k]>=0)return f[u][k];
	if(!k)return 0;
	
	int v[2],vi[2],tot=0;
	for(int i=0;i<g[u].size();i++)
		if(g[u][i].v!=fa)vi[tot]=i,v[tot++]=g[u][i].v;
	if(tot==0)return 0;
	
	f[u][k]=0;
	for(int i=k;i>=0;i--)
	{
		if(i<=size[v[0]]+1 && k-i<=size[v[1]]+1)
		{
			int w=0;
			if(i)w+=g[u][vi[0]].w+dfs(v[0],i,u);
			if(k-i)w+=g[u][vi[1]].w+dfs(v[1],k-i,u);
//			printf("{[%d,%d] %d_%d:%d}\n",u,k,i,k-i,w);
			f[u][k]=max(f[u][k],w);
		}
	}
	return f[u][k];
}
int main()
{
	memset(f,-1,sizeof f);
	cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		int u,v,w;cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	dfs_init(1,0);
	cout<<dfs(1,q+1,0);
	return 0;
}

#include<iostream>
#include<vector>
using namespace std;
int n,q,edge[101][101],sizee[101],dp[101][101]; //第几个节点,取几个
vector <int> g[101];

void dfs(int u){
    sizee[u]=1;
    for (auto i:g[u]){
        int v=i;
        dfs(v);
        sizee[u]+=sizee[v];
    }
    for (int j=1;j<=sizee[u]-1 && j<=q;j++){                        //以当前u为根节点保留的大小
        if (g[u].size()==2){                                        //两边都保留(前提是必须有两边)
            for (int k1=0;k1<=j-2;k1++){    
                int k2=j-2-k1;                                      //k1和k2表示保留的左右子树大小
                if (k1>sizee[g[u][0]] || k2>sizee[g[u][1]])continue;
                int tmp=0;                  
                tmp+=dp[g[u][0]][k]+edge[u][g[u][0]];
                tmp+=dp[g[u][1]][k2]+edge[u][g[u][1]];
                dp[u][j]=max(dp[u][j],tmp);
            }
        }
        for (auto v:g[u]){                                          //只保留一边的情况
            if (j-1>sizee[v]-1)continue;                            //如果留给当前子树的边数已经大于了当前子树的总边数
            dp[u][j]=max(dp[v][j-1]+edge[v][u],dp[u][j]);           //那么直接跳过
        }
    }
}


int main()
{
    cin >> n >> q;
    for (int i=1;i<=n-1;i++){
        int u,v,w;
        cin >> u >> v >> w;
        edge[u][v]=w;
        edge[v][u]=w;
        g[u].push_back(v);
    }
    dfs(1);
    cout << dp[1][q];


    return 0;
}