树形DP，f[j][i]表示有j个robot遍历i及其子树并且在此子树返回地球所需的最小值，但还有k个robot遍历子树i及其子树，再返回父亲节点m个机器人这种情况，但是可以证明这种情况一定不会是最优解，所以不予考虑。还有一个地方就是f[0][i]表示用0个robot遍历意思就是说用n个机器人遍历此子树，再返回，可知n=1，道理和前面那种情况的道理一样。在求f[i][j]是用的是分组背包的思想，刚开始多用了一个数组g[][]，来实现这个过程，后来看了其他人的代码，想了一想，可以用滚动数组优化，用f[i][j]就可以实现这个过程了
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
const int maxn=10000+10;
const LL inf=0x3f3f3f3f3f3f3f3f;
int e[2*maxn],head[maxn],cost[maxn*2],next[maxn*2],vis[maxn];
int n,s,k,tot;
LL f[maxn][11],g[maxn][11];
void dp(int x)
{
int i=head[x];
vis[x]=1;
if(next[i]==-1&&x!=s) return;//注意x!=s这一条件因为根可能只有一个子树
int p,q,w,tv;
int j;
for(;i!=-1;i=next[i])
{
tv=e[i];
if(!vis[tv])
{
dp(tv);
for(j=k;j>=0;j--)
{
f[x][j]=f[x][j]+f[tv][0]+2*cost[i];
for(q=1;q<=j;q++) f[x][j]=min(f[x][j],f[x][j-q]+f[tv][q]+q*cost[i]);
}
}
}
}
int main()
{
while(~scanf("%d%d%d",&n,&s,&k))
{
tot=0;
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(f,0,sizeof(f));
int i,u,v,c;
for(i=0;i<n-1;i++)
{
scanf("%d%d%d",&u,&v,&c);
e[tot]=v;
cost[tot]=c;
next[tot]=head[u];
head[u]=tot++;
e[tot]=u;
cost[tot]=c;
next[tot]=head[v];
head[v]=tot++;
}
dp(s);
printf("%I64d\n",f[s][k]);
}
return 0;
}