题意解析
题目告诉我们，A国有nnn座城市和n−1n-1n−1条道路，所有城市都能互相到达，这种没有环的结构在计算机里叫作"树"。现在你要开一辆货车从一号城市（首都）出发，把所有城市都走遍，最后不需要回到首都。我们的目标是让货车开过的总路程最短。
数据范围：城市数量n≤105n≤10^5n≤105,单条道路长度可达10910^9109.这暗示总距离极大，必须用long long储存；同时算法必须在O(n)O(n)O(n)左右的线性时间内完成，否则一定会超时。
抽丝剥茧：如何思考
1.朴素想法：全排列暴力搜索路线
面对"走遍所有点求最短路"的问题，最容易想到的是把所有可能的路线都试一遍:
第一步：列举所有访问顺序。假设我们要给出一个一次拜访城市的清单，比如先去2再去3，我们尝试把所有城市的排列组合全部列举出来。
第二步：模拟行走并计算距离。根据写好的清单，模拟货车在城市间移动。因为城市道路没有坏，任意两座城市之间只有唯一的最短路径。把清单上一路上经过的道路长度全部累加起来。
第三步：比较并选出最小距离。记录每一种路线清单算出的总距离，最后挑出那个最小的结果作为答案。
2.遇到瓶颈
我们来算算时间帐。对于nnn座城市，全排列的路线数量是n!n!n!(nnn的阶乘）。当n=12n=12n=12,
12!≈4.7∗10812!≈4.7 * 10^812!≈4.7∗108,对于每一条路线，我们需要写一个循环去模拟走过这12个城市，累加距离。这大约需要执行12次加法运算，所以运算量超过5∗1095*10^95∗109，彻底超时。本题n=105n = 10^5n=105,远大于12，更加会超时！这说明"纠结访问顺序"这条路走不通。
寻找规律与优化策略
假设A过只有4座城市，道路连接和长度如下：
上图可见
* 1号是首都
* 道路共有3条：12（长100）、13（长10）、3~4（长20）
* 所有道路长度之和 =100+10+20=130km= 100 + 10 + 20 = 130km=100+10+20=130km。
假设：要求"必须回到首都"
想想你是一个快递员，从111出发，要把包裹送到2,3,4,2,3,4,2,3,4,最后必须回111下班。
因为这地图没有环路（像树杈一样），走进死胡同就只能原路折返。
你的路线只能是这样(比如先去左边,再去右边):
出发1→2→1→3→4→3→11→2→1→3→4→3→11→2→1→3→4→3→1下班回家
我们来看看每条路你走了几次:
* 1到2的路: 去一次, 回一次 (走了2次)
* 1到3的路: 去一次, 回一次 (走了2次)
* 3到4的路: 去一次, 回一次 (走了2次)
发现规律了吗?
只要你最后回到起点,所有的路你都必定、且只能走恰好两次(一趟去, 一趟回)。
此时的总路程 === 所有道路之和的222倍$ = 130 * 2 = 260 km。$
这个260km260 km260km,是我们接下来计算的“基准线”。
题目真实情况“不用回首都”
现在老板说:“送到最后一个城市你就可以直接在那儿下班,不用回首都了!”
既然不用回首都,这意味着你最后停在哪个城市,从首都到那个城市的“回程路”就省下来了!
我们来看看停在不同城市的区别:
方案 A:最后停在4号城市(把4当最后一站)
* 路线:先去左边送2,折返回来,再去右边送3,4并在4下班。
* 实际走法: $1 → 2 → 1 → 3 4 $(停!)
* 算算每条路走了几次:
* 1-2 道路:走了222次(去,回)
* 1-3 道路:走了111次(去了就没回来)
* 3-4 道路:走了111次(去了就没回来)
* 实际总路程:100×2+10×1+20x1=230km100 × 2 + 10 × 1 + 20 x 1 = 230 km100×2+10×1+20x1=230km。
* 230=260−30230 = 260-30230=260−30。(即:总路程的222倍- 首都到444号城市的距离)
方案 B:最后停在2号城市(把2当最后一站)
* 路线:先去右边送3,4,折返回来,再去左边送2并在2下班。
* 实际走法: 1→3→4→3→1→21 → 3 → 4 → 3 → 1 → 21→3→4→3→1→2(停!)
* 算算每条路走了几次:
* 1-3 道路:走了222次(去,回)
* 3-4 道路:走了222次(去,回)
* 1-2 道路:走了111次(去了就没回来)
* 实际总路程:10×2+20×2+100x1=160km10 × 2 + 20 × 2 + 100 x 1 = 160 km10×2+20×2+100x1=160km。
* 160=260−100160 = 260 - 100160=260−100。(即:总路程的2倍- 首都到2号城市的距离)
总结:
通过对比方案A(230km)A(230 km)A(230km)和方案 B(160km)B (160 km)B(160km),方案 B 明显更短,也就是题目要求的“最小化路程”。
为什么方案更短?
因为方案 BBB最后一站选了222号城市,而1到2的距离是100km100 km100km。
你把哪座城市作为最后一站,你就能省下首都到那座城市的折返距离。
我们要想让货车开的总路程最短,当然是希望省下来的回程路越长越好!
这就好比你有两张抵扣券,一张抵扣303030元,一张抵扣100100100元,为了花钱最少,你肯定用那张100100100元的对不对?
所以:
想让总路程最小要减去的回程路必须最大必须把离首都最远的城市作为最后一站。
最终顺理成章得出公式:最短总路程===所有道路总长 x $2 - $首都到最远城市的距离。
优化后的解题过程:
第一步:搭建地图并累加路程(准备基准线)
在读取数据的同时做两件事:一是把城市间的双向连接关系存进数组(代码里的eee);二是顺手把所有道路的长度累加到变量中,为后面计算sss×222做准备。
第二步:寻找最远城市(找出能“省下”的最长路)
写一个DFS(深度优先搜索) 函数,从首都(111号)开始顺着路一直往下探。
* 每走到一个城市,就看看当前距离是不是打破了最远纪录,如果是,就更新给变量mxmxmx。
* 为了防止“原地打转”,每次往下走时,都避开刚才过来的那个城市(不走回头路)。
第三步:套用公式,一秒出结果
探路结束后,地图的总路长sss和最远距离 mxmxmx 都拿到了。直接让计算机输出sssx222-mxmxmx,不需要任何复杂的路径模拟,直接得出最短总路程!
复杂度分析
通过上述推导,我们只需要把所有路权加起来,再顺着道路找一遍离首都最远的城市即可。时间复杂度为O(N)O(N)O(N),空间复杂度为O(N)O(N)O(N),这个复杂度能在规定时间内轻松通过全部测试点!
