依赖背包变形——hdu4003

/*
dp[u][j]为在子树u有j个机器人不回来 
*/
#include<bits/stdc++.h>
using namespace std;
#define N 10005
struct Edge{int to,nxt,w;}e[N<<1];
int head[N],tot,n,k,s;
void init(){
    memset(head,-1,sizeof head);tot=0;
}
void add(int u,int v,int w){
    e[tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot++;
}
int dp[N][20];
void dfs(int u,int pre){
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dfs(v,u);
        for(int j=k;j>=0;j--){
            dp[u][j]=2*e[i].w+dp[v][0]+dp[u][j];
            for(int l=1;l<=j;l++)
                dp[u][j]=min(dp[u][j],dp[u][j-l]+dp[v][l]+l*e[i].w);//给v子树l个机器人 
        }
    }
}

int main(){
    while(cin>>n>>s>>k){
        init();
        for(int i=1;i<n;i++){
            int u,v,w;scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        memset(dp,0,sizeof dp);
        dfs(s,s);
        int ans=0x3f3f3f3f;
        for(int i=0;i<=k;i++)
            ans=min(ans,dp[s][i]);
        cout<<ans<<‘\n‘;
    }
    return 0;
}