题意

• 对于一个有n个结点的二叉树，根的编号一定为1，每条边有权值
• 求保留q条边时，最多能获得多少权值
• tip:分析样例可以知道，这棵树的根是必须保留的，“剪枝行为”一定是保留根含有根的子树

思路

• 由于输入是无规律的输入每一条边，所以应当先建立起二叉树，从根开始深搜建树
• 由于边权是较难处理的，我们发现可以把所有边权变为该条边所连的儿子的权值，把边权转换为点权，同时边转化为点，会多一个点，所以最终保留q条边会变为保留q+1个点
• 建完这棵树后，可以进行动态规划，对每个结点考虑剩下多少个边，进行枚举

• 表示i包含j个点(边)
• 树形dp，dfs深搜即可，每次深搜记录当前结点和剩余结点数，从当前层迭代到下一层只需改变剩余结点数即可

代码

#include<bits/stdc++.h>
using namespace std;

/**
 * dp[i][j]表示i包含j个点(边)
 * dp[i][j]=dp[T[i].l][k]+dp[T[i].r][j-1-k];
 */


typedef struct node{
    int val;
    int l,r;
}tree;
tree T[200];
vector<int> g[150];
int v[150][150];
int dp[150][150];
int n,q;

void push_down(int x,int fa){
    for(auto i : g[x]){
        if(i==fa)continue;

        if(T[x].l==0) T[x].l=i;
        else T[x].r=i;

        T[i].val=v[x][i];            
        push_down(i,x);
    }
}
int dfs(int x,int rst){
    if(x==0) return 0;
    if(dp[x][rst]!=0) return dp[x][rst];
    for(int i=0;i<rst;i++){
        dp[x][rst]=max(dp[x][rst],dfs(T[x].l,i)+dfs(T[x].r,rst-1-i)+T[x].val);
    }
    return dp[x][rst];
}

int main(){
    cin >> n >> q;
    for(int i=1;i<n;i++){
        int a,b,c;
        cin >> a >> b >> c ;
        g[a].push_back(b);
        g[b].push_back(a);
        v[a][b]=v[b][a]=c;
    }
    push_down(1,0);
    // for(int i=1;i<=n;i++){
    //     cout << i << ' ' << T[i].val << ' ' << T[i].l << ' ' << T[i].r << endl;
    // }
    cout << dfs(1,q+1) << endl ;
    return 0;
}