树的直径

树的直径定义和求法都很简单，但是它有许多神奇的性质和用法，在树上问题中十分重要。

定义

一棵树中最长的简单路径称为树的直径。 树的直径可能有一个或多个；当然，一棵树的直径长度总是唯一的。

比如上图中的直径就是：$4-2-1-3-7$，以及 $5-2-1-3-7$ 等四条。

下文将从 u 到 v 的简单路径简记为 $\delta(u,v)$。

DFS 求法

树的直径有很多求法，时间复杂度都是 $O(n)$。不过我比较喜欢用 DFS 求直径。DFS 求法要求树的权值为正或没有权值。做法如下：

• 从任意节点出发做 DFS，找到树上离这个节点最远的节点 $u$。

• 从 $u$ 出发，找到树上离这个节点最远的节点 $v$。

• $\delta(u,v)$ 即树的一条直径。

这个方法的正确性在后面的“性质”中有证明。

性质（定理）

树的直径有很多神奇的性质。

正边权树上，所有直径的中点重合

反证法：

• 假设正边权树上的两条中点不重合的直径 $\delta(u_1,v_1)=\delta(u_2,v_2)$，中点分别是 $x_1,x_2$。

• 

  图摘自 oi-wiki

• 则存在一条路径 $\delta(u_1,v_2)=\delta(u_1,x_1)+\delta(x_1,x_2)+\delta(x_2,v_2)$。

• 而由中点可知 $\delta(x_2,v_2) = \delta(x_1,v_1)$，于是 $\delta(u_1,x_1)+\delta(x_2,v_2)=\delta(u_1,v_1)$。

• 于是 $\delta(u_1,v_2)=\delta(u_1,v_1)+\delta(x_1,x_2)\gt\delta(u_1,v_1)$，我们找到了一条比直径更长得路径。矛盾。

证毕。

正边权树上，离任意点最远的点是直径的端点

这也是 DFS 方法为什么正确的原因。反证法：

• 假设离树上点 $x$ 最远的点为 $y$，它们之间的路径 $\delta(x,y)$ 称为 $x$ 的最远路径。假设 $y$ 不是任何直径的端点。假设树的一条直径为 $\delta(u,v)$，

• 如上图，如果 $x\in\delta(u,v)$，那么：

  • 如果 $y_1\in\delta(u,v)$，因为 $y$ 不是直径端点，所以必然有 $\delta(x,v)=\delta(x,y_1)+\delta(y_1,v)\gt\delta(x,y_1)$。矛盾。

  • 如果 $y_2\notin\delta(u,v)$，那么当且仅当 $\delta(x,y_2)\gt\delta(x,v)$ 时，$\delta(x,y_2)$ 才能成为最长路径。如果这样，那么

    $\delta(u,x)+\delta(x,y_2)\gt\delta(u,x)+\delta(x,v)$，即 $\delta(u,y_2)\gt\delta(u,v)$。矛盾。

  • $y$ 处于 $y_3$ 位置时与 $y_2$ 同理。

• 如上图，如果 $x\notin\delta(u,v)$，那么：
  • 如果 $y_1\in\delta(u,v)$，当然有 $\delta(x,u)=\delta(x,y_1)+\delta(y_1,u)\gt\delta(x,y_1)$。矛盾。
  • 如果 $y_2\notin\delta(u,v)$，那么需要满足 $\delta(x,y_2)\gt\delta(x,v)$，那么 $\delta(u,y_2)\gt\delta(u,v)$。矛盾。
  • $y$ 处在 $y_3$ 位置时与 $y_2$ 同理。

证毕。