先动最左边的部分，在动最右边，基本上就妥

树形dp。 其实，我觉得能够定义合适的状态，问题就解决了一半了。 因为一个机器人遍历完一颗子树可能返回到父亲节点，所以我定义dp[u][i]表示遍历完以u为根的子树的所有边时使用i个机器人并且这i个机器人都不回到u的最小代价（不会再在遍历别的子树时被使用）。 但是要考虑到可能对于一颗子树他独自用到的机器人是0个，其实这就可以用dp[u][0]表示了。在这种情况下会有几个机器人进去呢？答案是进去一个是最优的，因为有p个机器人进去又出来的话，在父亲与儿子的边上走了p∗2遍，但是在儿子子树的内部的花费都是一样的，都是边权和乘以2，，所以进去一个机器人是最优的。 接下来考虑状态转移。我们对于节点u遍历它的每一个儿子v，我们用类似滚动数组的方法(?)滚动记录dp[u][i]的最优解，用cost表示父亲u和儿子v之间的边权。 首先从dp[v][0]转移：

dp[u][i]=dp[u][i]+dp[v][0]+cost∗2

枚举v消耗了j个机器人： dp[u][i]=min(dp[u][i],dp[u][i−j]+dp[v][j]+j∗cost)

需要注意i从K到0枚举，j从1到i枚举，并且先dfs再枚举。 答案就是dp[root][k]。 时间复杂度：O(n*K2)