1. 题目

传送门=￣ω￣=

2. 题解

先遍历一遍图，建立二叉树。
再树型 dp 即可，对于当前节点，枚举给它左儿子多少，右儿子多少。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,q,f[105][105],l[105],r[105],ld[105],rd[105];
vector<int> g[105],dg[105];
bool book[105];
void init(int u)
{
    book[u]=1;
    for(int i=0;i<g[u].size();i++)
        if(!book[g[u][i]])
        {
            if(!l[u])l[u]=g[u][i],ld[u]=dg[u][i],init(g[u][i]);
            else r[u]=g[u][i],rd[u]=dg[u][i],init(g[u][i]);
        }
}
int dfs(int u,int d)
{
    if(f[u][d]>-1)return f[u][d];
    if(f[u][d]=0,!u||!d)return 0;
    for(int i=0;i<d;i++)
        f[u][d]=
            max(f[u][d],dfs(l[u],i)+dfs(r[u],d-i-1)+ld[u]*(i>0)+rd[u]*(d-i-1>0));
    return f[u][d];
}
int main()
{
    scanf("%d%d",&n,&q),memset(f,-1,sizeof(f));
    for(int i=1,a,b,c;i<n;i++)
        scanf("%d%d%d",&a,&b,&c),
        g[a].push_back(b),g[b].push_back(a),dg[a].push_back(c),dg[b].push_back(c);
    init(1),printf("%d\n",dfs(1,q+1));
    return 0;
}