题意：给出n个点的一棵树，有k个机器人，机器人从根节点rt出发，问访问完整棵树(每个点至少访问一次)的最小代价(即所有机器人路程总和)，机器人可以在任何点停下。
解法：这道题还是比较明显的能看出来是树形DP，然后分配机器人肯定想到树形分组背包DP。那么dp方程和常规树形背包dp一样很容易些 dp[x][i]=min(dp[x][i],dp[y][j]+val(y,j)+dp[x][i-j]) 代表总共i个机器人给当前子树y分配j个机器人剩下的i-j个机器人分配给前几棵子树的最小代价。主要问题就是转移代价怎么写？明显如果机器人数量>=叶子结点数量就直接每个叶子派一个就行，否则必须得重复使用。仔细观察得到其实只要特殊处理派机器人为0的情况就行，派机器人>0的直接dp，且容易得到派机器人为0就是的代价就是 子树大小*2 （因为要从分叉点进去访问这棵子树之后再回到这个分叉点，画图很容易理解）。所以特殊处理机器人=0，其他代价就是dp[y][j]+j*w。有点绕，配合代码看会容易理解一些。
总的来说，这是一道好题，不容易想很锻炼思维(至少对博主来说是这样)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+;
int n,m,rt;
int siz[N],dp[N][],tmp[]; int cnt,head[N],nxt[N<<],to[N<<],len[N<<];
void add_edge(int x,int y,int z) {
nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt;
} int calc(int y,int k,int i) {
if (k==) return dp[y][k]+*len[i]; else return dp[y][k]+k*len[i];
} void dfs(int x,int fa) {
siz[x]=;
bool ok=;
memset(dp[x],0x3f,sizeof(dp[x])); dp[x][]=;
for (int i=head[x];i;i=nxt[i]) {
int y=to[i];
if (y==fa) continue;
dfs(y,x); ok=;
siz[x]+=siz[y]+len[i];
memcpy(tmp,dp[x],sizeof(dp[x]));
memset(dp[x],0x3f,sizeof(dp[x]));
for (int j=m;j;j--)
for (int k=;k<=j;k++) //给子节点y分配k个机器人
dp[x][j]=min(dp[x][j],calc(y,k,i)+tmp[j-k]);
dp[x][]=*siz[x];
}
if (ok) memset(dp[x],,sizeof(dp[x]));
} int main()
{
while (scanf("%d%d%d",&n,&rt,&m)==) {
cnt=; for (int i=;i<=n;i++) head[i]=;
for (int i=;i<n;i++) {
int x,y,z; scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z);
add_edge(y,x,z);
}
dfs(rt,);
int ans=0x3f3f3f3f;
for (int i=;i<=m;i++) ans=min(ans,dp[rt][i]);
printf("%d\n",ans);
}
return ;
}