树的直径

定义

所谓树的直径，就是树上一条最长的链。

注意到这条链不唯一。

我决定在讲解例子的过程中穿插性质。

直径的求法

两次搜索

引理：一棵树上以任意一个点开始的最长简单路径的终点一定是直径两个端点之一。

证明：

若不是端点，可分为两种情况讨论：
第一种，这条路径不与直径相交，则让直径改道过来这条路径显然比原来的直径更长，矛盾。
第二种，这条路径与直径相交，则让直径在交点处顺着这条路径走显然比原来直径更长，矛盾。
得证。

所以我们可以两次搜索。

第一次任选一个点当做起点，找到距离这个点最远的一个点，则这个点一定是直径的其中一个端点。

第二次再把这个端点当做起点，找到另一个端点。

这种方法的好处在于可以求具体方案。但是注意一棵树可能有多条直径，且这种方法不适用于负权边存在的情况。

树形 DP

在树形 DP 中，我们对于每个点维护两个值：在以这个点为根的子树中，从这个点往下走的链的最长长度和次长长度。转移直接由儿子的最长长度加上到儿子的边权即可。

直径就是每个点最长长度和次长长度加起来的最大值。

这种方法可以用于负权边情况。

[SDOI2011] 消防（树网的核 加强版）

题意不再赘述。

首先说说为什么这条路径肯定在直径上。我们只要证明当这条路径不在直径上的时候，不比在直径上更优即可。

依然分两种情况。
首先，在这棵树上，存在一个点，使得它到直径两端的距离的最大值最小（也即到其他任何点的距离最大值最小）。这个点一定是在直径上的。
当这条路径完全不在直径上时，还不如直接选取这个点更优，而这个点的路径长度是 $0$，肯定比这个路径更优。
当这条路径有一部分在直径上时，直接把不在直径上的部分去掉，让它变成一条完全在直径上的路径，答案不会变。因为如果答案变了，说明把这条路径不在直径上的部分去掉后，路径的端点顺着原路径方向的距离最大值比到直径端点的距离长，与 “一棵树上以任意一个点开始的最长简单路径的终点一定是直径两个端点之一” 相矛盾。

所以我们只需要考虑这条路径在直径上即可。

考虑对于一条直径上的路径，如何计算它到各点路径长度的最大值。

首先，这条路径的左右端点到直径的左右端点的距离可能成为最大值，这是显然的，而且我们不用考虑左右端点到除了直径端点以外的情况，因为 “一棵树上以任意一个点开始的最长简单路径的终点一定是直径两个端点之一”。

我们给直径做一个距离前缀和，就能快速求出来这个距离。

其次，路径上中间的每个点还可以往直径的侧边走，我们对于直径上每个点预处理出来往侧边走的最大值。

最后考虑如何维护路径。

我们使用双指针来维护 “路径长度不超过 $s$” 这一条件，用单调队列来维护路径上点往侧边走的最大值即可。最终 $O(n)$。

树的半径

还是挺重要的。

定义

在一棵树中，找到一个点（中心）使得这个点到树的其他所有点的距离最大值最小，则这个最大值就是树的半径。

求法

先用树形 DP 求直径把 $f_u,g_u$ 求出来。

定义 $h_u$ 为 $u$ 这个结点往上走的最大距离。转移考虑两种情况：$u$ 到父亲继续往上走，还是 $u$ 到父亲然后到 $u$ 的兄弟，两种情况取 $\max$ 即可。

半径就是所有 $\max\{f_u,h_u\}$ 的最小值。

直径的合并

挺有意思的。标题没打错，就是 直径 的合并。

对于两棵树，把它俩合并之后直径的长度最小是多少？

两种情况：

第一种情况，是原来两棵树的直径不变。

第二种情况，两棵树的中心连起来，最终的直径就是两棵树的半径和连起来这条边的边权加起来。

很显然，不多说了。