别骂了别骂了，我确实标题党。

题解直接告诉你我们要找一个最长的哈密顿回路然后去掉一条边，但是这其实是很没有道理的——为啥不可能会出现一条短一点的哈密顿回路，然后去掉一条短一点的边，最后得到一条更长的哈密顿路径呢？

以只有一个重心的情况为例。如果一条哈密顿回路，使得重心的每条邻边被经过的次数都取到了最大值，那么可以发现其他每条边被经过的次数也取到了最大值，也就是说这条哈密顿回路一定是最长的哈密顿回路。

那么，一条不是最长的哈密顿回路，至少有一条重心的邻边被经过的次数没有取到最大值，也就是说它至少比最长的哈密顿回路少了这条边的边权的两倍——那就比我们找到的哈密顿路径短了，再去掉一条边只会更短，所以我们找到的哈密顿路径一定是最优的。

两个重心的情况也是类似的。

另外这题题解都很不严谨，少了一堆证明，不过真要证起来也不是很难，我也懒得写了。