这题其实是有 \(O(n)\) 的解法的
我们考虑枚举删掉边的中间点，把树分成两个部分
然后对两棵树求直径中点，让删掉的边连接两个树的中点即可
最终复杂度 \(O(n^2)\)
如果通过加一条边操作让直径最小，则我们考虑把两棵树的中点相连
然后我们考虑 \(O(n)\) 的解法
首先，我们删的边一定在原树的直径上，否则删完边后不会对直径产生影响
因此我们考虑枚举直径上删哪条边，然后还是两遍 \(dfs\) 暴力找直径
我们再考虑优化，我们发现在删掉边后树的直径端点的一段一定是原直径的端点。因此我们一边 \(dfs\) 即可完成
但还是不够优秀，我们发现我们在计算答案时 \(dfs\) 了很多重复的情况
我们考虑从左到右考虑删哪条边，我们发现每向右移动一条要删的边，左边的树就多出来了红色的我们没有搜索的部分
我们何尝不只搜索红色的节点，然后更新左边的树的直径呢
这样找树的直径就可以做到 \(O(n)\) 了
但是还没完，我们还要考虑怎么找树的中点
我们发现在删边的过程中，左边树的直径长度显然是单增的
因此树的中点位置显然也只会向右移动，因此我们考虑每次修正中点的位置即可
我们在从左到右删完边，考虑完左边树的部分后，我们再从右到左求一边右边树，然后合并答案即可
最终复杂度 \(O(n)\)
此做法的思路是：
-
发现删的边只可能是直径上的边
-
发现删掉边后树的直径的一个端点是原树直径的一个端点
-
发现加点比删点容易，改变搜索顺序
-
发现有搜索重复的部分，优化
-
考虑直径长度有单调性，优化