有n个城市（编号从1到n），它们之间通过双向的道路相连。那里只有n－1条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。 一天，某个游客到了编号为k的城市。他计划从城市k开始，游遍所有的城市m1，m2，m3……，mi，…（不一定要按这个顺序旅游）。每个城市mi都是不同的，并且，也与k不同。他想要以最短的路程旅行完所有的城市（从城市k开始）。求旅游完上述的城市最短需要多少路程。
提高部分：输出最短旅程的详细旅游路线

这不就是最短路径问题吗

目测树形dp

明显树形dp，按道理树形dp节点数基本上是10万，如果枚举终点，不好意思，肯定tle。其实这题一遍dfs就可以了，比较简单。从一个节点出发的最小费用就是遍历某些子树回来，然后遍历唯一颗子树不回来的费用和。dp数组维护即可，路径保存不回来的那颗子树就好了。这个题目的升级其实是不知道起点在哪，要你求最小费用。要枚举起点吗，然后每一次都用刚才的树形dp吗，不用，这样做也是tle的，这个必须来两遍dfs，因为一遍dfs我们只能得到子树的完全信息，而无法知道父节点那边信息，其中根节点最优可以确定，因为它没有父节点，显然可以确定的。第二遍dfs可以将根节点的信息传下来，由根出发的最小花费已经确定推出其他点的最小花费，取所有的最小花费最小的，这就是第二遍dfs要干的事。有问题欢迎指正。

用一个数组pre[]记录前驱，更新即可

呃，还有源码嘛