树形背包的变形，要特殊考虑当用一个机器人遍历一棵子树的情况。
/* d[i][k]表示节点i用k个机器人探索的最小花费 跟树型背包问题差不多d[u][k]=d[u][k-i]+d[v][i]+i*w 表示给当前已遍历的子树以及父节点k-i个机器人,给当前正在遍历子树i个机器人 注意也可以把k个机器人全部给已遍历子树,d[v][0]实际上相当于用一个机器人遍历完再走到父节点 所以这种情况下d[u][k]=d[u][k]+d[v][0]+2*w */ #include <stdio.h> #include <string.h> #define MAXN 10005 #define MAXK 11 typedef __int64 LL; int n,s,k,tu,tv,tw; struct edge{ int v,w,n; }e[MAXN*2]; int first[MAXN],es; void addedge(int u,int v,int w){ e[es].v=v,e[es].w=w,e[es].n=first[u],first[u]=es++; } LL d[MAXN][MAXK]; inline int min(int x,int y){return x<y?x:y;} void dp(int u,int f){ for(int i=first[u];i!=-1;i=e[i].n){ int v=e[i].v; if(v==f)continue; dp(v,u); for(int i1=k;i1>=0;i1--){ d[u][i1]+=d[v][0]+2*e[i].w; for(int i2=1;i2<=i1;i2++) d[u][i1]=min(d[u][i1],d[u][i1-i2]+d[v][i2]+i2*e[i].w); } } } int main(){ //freopen("test.in","r",stdin); while(scanf("%d%d%d",&n,&s,&k)!=EOF){ memset(first,-1,sizeof first);es=0; for(int i=0;i<n-1;i++){ scanf("%d%d%d",&tu,&tv,&tw); addedge(tu,tv,tw); addedge(tv,tu,tw); } memset(d,0,sizeof d); dp(s,-1); printf("%I64d\n",d[s][k]); } return 0; }