我个蒟蒻赛时连 T1 都没切，但是这个 T2 真的很水啊。
$$\texttt{Solution}$$
难度不高，爆想了 10 分钟有了一个贪心的思路，来看这张图理解一下：
这就是一个比较简单的例子，我们考虑从它推演到一般情况。
因为需要从首都出发经过所有的城市，所以当我们去到 \(2\) 号城市又想去 \(3\) 号城市时，我们必须要先回到首都才能重新去到 \(3\) 号城市。因为这是一棵树，树上 \(2,3\) 两点是叶子结点，到了 \(2\) 必须先回到根才能到达 \(3\)。从 \(3\) 号结点到 \(4\) 号节点也同理。
题目里还说了一点：
最后不一定要返回根结点。
这说明我们最后可以停在一个结点。
经过刚才的观察我们会发现，几乎所有到叶子结点的路径我们都要走两遍，因为如果我们要去到另一个未到达过得结点已经无路可走了，必须要绕回根结点再重新走。但是到最后一条路径时，我们已经走完了所有的点，不必再回头了。
那为了少走路，我们肯定会选择最长的那一条路径最后再走。那么就可以写出来了。
讲一下具体步骤：
- 先跑一遍 dfs，用 \(dis\) 数组求出到叶子结点最长的那条路径和所有叶子结点。
- 设答案一开始加上所有边权的两倍，然后减掉到叶子结点最长的那一条路径，输出即可。
讲个笑话：作者脑子抽了，一开始当成图论题了，以为要先求最小生成树再用最短路。后来发现本来就是树，就用我这个思路写的 dfs 加最短路。赛后才想起来树上的路径是唯一的，一遍 dfs 就可以解决啊！这都能过。
时间复杂度 \(O(n)\)。