题意：求k个机器人从同一点出发遍历整棵树所要的最小花费。树中边有权值。
分析：
1、这是带回溯的树形dp，和apple tree一样。这题是边权，apple tree是点权。
2、很明显是至少有一个机器人遍历整棵树。分给子树遍历的机器人越多，从子树的根回到它的父节点走
的重复路程也越多。“至少有一个”联想到分组背包。
3、dp[i][0]表示1个机器人遍历整棵树，不分给以i为根节点的树的子树另外的机器人。
把总的机器人个数当做背包容积，边权当作价值。
for(int j=V；j>=0;j--)
for(int k=1;k<=j；k++)
dp[s][j]=min(dp[s][j],dp[s][j-k]+dp[v][k]+edge(s,v)*k)；
分k（1<=k<=j)个机器人遍历v为根的子树。
为了保证至少选一个，先把dp[v][0]放入背包。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[10010][12],head[10010];
int V,tot;
struct node
{
int to,val;
int next;
}edge[10010*2];
int minn(int a,int b)
{
return a<b?a:b;
}
void add(int x,int y,int c)
{
edge[tot].to=y;
edge[tot].val=c;
edge[tot].next=head[x];
head[x]=tot++;
}
void init()
{
memset(dp,0,sizeof(dp));
memset(head,-1,sizeof(head));
tot=0;
}
void dfs(int u,int pre)
{
int i;
for(i=head[u];i!=-1;i=edge[i].next)
{
int t=edge[i].to;
if(t==pre) //如果t是父亲节点continue;
continue;
dfs(t,u);
for(int j=V;j>=0;j--)
{
dp[u][j]+=dp[t][0]+2*edge[i].val; //保证至少选一个
for(int k=1;k<=j;k++)
dp[u][j]=minn(dp[u][j],dp[u][j-k]+dp[t][k]+k*edge[i].val);
}
}
}
int main()
{
int n,s,a,b,cost;
while(scanf("%d%d%d",&n,&s,&V)!=EOF)
{
init();
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&a,&b,&cost);
add(a,b,cost);
add(b,a,cost);
}
dfs(s,-1);
printf("%d\n",dp[s][V]);
}
return 0;
}