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