树的直径

树中所有最短路径距离的最大值是树的直径。

此方法适用于求 边权均非负 的树的直径。

首先对任意一个结点做 DFS 求出最远的结点，然后以这个结点为根结点再做 DFS 到达另一个最远结点。第一次 DFS 到达的结点可以证明一定是这个图的直径的一端，第二次 DFS 就会达到另一端。下面来证明这个定理。（参考资料）

但是在证明定义之前，先证明一个引理：

引理：在一个连通无向无环图中，$x$、$y$ 和 $z$ 是三个不同的结点。当 $x$ 到 $y$ 的最短路与 $y$ 到 $z$ 的最短路不重合时，$x$ 到 $z$ 的最短路就是这两条最短路的拼接。

证明：假设 $x$ 到 $z$ 有一条不经过 $y$ 的更短路 $\delta(x,z)$，则该路与 $\delta(x,y)$、$\delta(y,z)$ 形成一个环，与前提矛盾。

定理：在一个连通无向无环图中，以任意结点出发所能到达的最远结点，一定是该图直径的端点之一。

证明：假设这条直径是 $\delta(s,t)$。分两种情况：

当出发结点 $y$ 在 $\delta(s,t)$ 时，假设到达的最远结点 $z$ 不是 $s,t$ 中的任一个。这时将 $\delta(y,z)$ 与不与之重合的 $\delta(y,s)$ 拼接（也可以假设不与之重合的是直径的另一个方向），可以得到一条更长的直径，与前提矛盾。
当出发结点 $y$ 不在 $\delta(s,t)$ 上时，分两种情况：
- 当 $y$ 到达的最远结点 $z$ 横穿 $\delta(s,t)$ 时，记与之相交的结点为 $x$。此时有 $\delta(y,z)=\delta(y,x)+\delta(x,z)$。而此时 $\delta(y,z)>\delta(y,t)$，故可得 $\delta(x,z)>\delta(x,t)$。由 1 的结论可知该假设不成立。
- 当 $y$ 到达的最远结点 $z$ 与 $\delta(s,t)$ 不相交时，记 $y$ 到 $t$ 的最短路首先与 $\delta(s,t)$ 相交的结点是 $x$。由假设 $\delta(y,z)>\delta(y,x)+\delta(x,t)$。而 $\delta(y,z)+\delta(y,x)+\delta(x,s)$ 又可以形成 $\delta(z,s)$，而 $\delta(z,s)>\delta(x,s)+\delta(x,t)+2\delta(y,x)=\delta(s,t)+2\delta(y,x)$，与题意矛盾。

因此定理成立。

我们记录当 $1$ 为树的根时，每个节点 $u$ 作为子树的根向下所能延伸的最远距离 $f_{u,0}$ 和次远距离 $f_{u,1}$，那么直径就是所有 $f_{u,0}+f_{u,1}$ 的最大值。

例题