【NOI2002】贪吃的九头龙（树上背包）

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define bmn lkx266404225
#define ll long long
const int N=305;
using namespace std;
template<class T>
inline void read(T &x)
{
    x=0; int f=1;
    static char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    x*=f;
}
int n,m,k;
int dp[N][N][2];
struct Edge
{
    int to,next;
    int val;
}edge[2*N];
int tot,first[N];
inline void addedge(int u,int v,int w)
{
    tot++;
    edge[tot].to=v; edge[tot].next=first[u]; edge[tot].val=w; first[u]=tot;
}
int tmp[N][2];
void dfs(int now,int fa)
{
    dp[now][0][0]=dp[now][1][1]=0;
    for(int u=first[now];u;u=edge[u].next)
    {
        int vis=edge[u].to;
        if(vis==fa)	continue;
        dfs(vis,now);
        memcpy(tmp,dp[now],sizeof(tmp));
        memset(dp[now],0x3f,sizeof(dp[now]));
        for(int i=0;i<=k;i++)
        {
            for(int j=0;j<=i;j++)
            {
                dp[now][i][0]=min(dp[now][i][0],min(dp[vis][j][0]+tmp[i-j][0]+(m==2)*edge[u].val,dp[vis][j][1]+tmp[i-j][0]));
                dp[now][i][1]=min(dp[now][i][1],min(dp[vis][j][0]+tmp[i-j][1],dp[vis][j][1]+edge[u].val+tmp[i-j][1]));
            }
        }
    }
    
}
int main()
{
    read(n),read(m),read(k);
    if(n-k<m-1){puts("-1");return 0;}
    for(int i=1,u,v,w;i<=n-1;i++) read(u),read(v),read(w),addedge(u,v,w),addedge(v,u,w);
    memset(dp,0x3f,sizeof(dp));
    dfs(1,0);
    cout<<dp[1][k][1];
    return 0;
}