Description：

给出一棵树，求断开一条边再接上一条边后新树的直径最小值。

$1\leqslant n\leqslant 300000$

Solution：

首先有结论：设两棵小树的直径为 $l_1,l_2$ ，那么加一条边的新树直径最小值为 $\max(l_1,l_2,\lceil\frac{l_1}2\rceil+\lceil\frac{l_2}2\rceil+1)$ ，于是可以求出某一棵子树的直径和整棵树去掉这个子树的直径，然后用上面那个公式计算，具体的计算方法是可以把这个点的直径更新上面的答案，这样可以求出某个子树的直径，去掉子树的直径可以二次扫描加换根，即每次把别的子树的直径最大值更新到这个子树上来，类似树上最长链的做法，然后在这个点维护一个子树前缀最大值和子树后缀最大值就可以计算去掉这个子树的最大值了。

Code：

没有代码