题意

• 对于一个有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;
}

思路（法二）

• 就硬存每一条边
• 考虑为背包，把父亲和剩下的看为一部分，把当前及子树看为一部分
• 注意更新的时候先更新大的部分再更新小的部分，不然大的取最优会取重复

代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
vector<int> g[120];
vector<int> apple[120];
int dp[300][300];
void dfs(int x,int fa){
    dp[x][0]=0;
    for(int id=0;id<g[x].size();id++){
        int i=g[x][id];
        if(i==fa) continue;
        dfs(i,x);
        for(int j=q;j>=0;j--){
            for(int k=0;k<j;k++){
                dp[x][j]=max(dp[x][j],dp[x][j-k-1]+dp[i][k]+apple[x][id]);
            }
        }
    }

}

int main(){
    cin >> n >> q ;
    for(int i=1;i<n;i++){
        int x,y,val;
        cin >> x >> y >> val;
        g[x].push_back(y);
        g[y].push_back(x);
        apple[x].push_back(val);
        apple[y].push_back(val);
    }
    dfs(1,0);
    cout << dp[1][q];
    return 0;
}