algorithm - 寻找访问许多城镇的最短路径

我遇到这个问题，不知道怎么解决。有人能帮我一下吗？
有N个城镇通过N-1条道路相连，任意2个城镇之间有一条道路。每条道路都有正相关成本，该国的城市C有2条道路与之相连（城市也是其中一个城镇），而其他城镇有1条或3条道路与之相连。
我们想从C市开始旅行，访问M个不同的城镇（1

最佳答案

这个图是根C的aBinary Tree。
我想出了一个O(n^3)算法，主要使用Dynamic Programming
dp[i][j]存储i-th城镇的最短路径值，访问其子树中的不同城镇我们很容易找到
j
这意味着访问左子树的dp[i][j] = min (dp[sonl][k] + dp[sonr][j-k-1] + 2*wl + 2*wr | 1<=k<=j-1)城镇和右子树的k城镇，j-k-1和sonl是sonr城镇的两个儿子，i-th和wl是wr到i和sonl之间的距离。

关于algorithm - 寻找访问许多城镇的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33229454/