「45」树的直径

定义

备注

给定一棵树，树中每条边都有一个权值，树中两点之间的距离定义为连接两点的路径上的边权之和。树中最远的两个节点之间的距离被称为 树的直径。

危险

下面我们讨论的前提均为边权非负。

性质1

提示

从任意点出发，最远点一定可以作为某条直径的端点。

任取一个点 $s$，找到距离 $s$ 最远的点 $A$。那么 $A$ 一定是某条直径的端点。再从 $A$ 出发，找到最远点 $B$，则 $A\rightarrow B$ 就是一条直径。

证明

将 $s$ 作为根节点，任取树的一条直径 $U \sim V$， $U$ 和 $V$ 的 LCA 为点 $T$。考虑 $U$ 和 $A$ 的LCA 点 $P$ 与 $T$ 的位置关系。

情况1

点 $P$ 位于 $T$ 和 $S$ 之间，包括 $T$ 和 $S$。

因为 $SA \ge SV$，所以 $PA \ge PV$，所以 $PU + PA \ge TU + TV$。

而 $UV$ 已经是树的一条直径，是树中所能得到的两点间的最长距离。所以 $UA$ 也是树的直径。因此 $A$ 是某条直径的端点。

从直径的一个端点出发，找到的最远点就是直径的另一个端点。

情况2

点 $P$ 位于 $T$ 和 $U$ 之间，包括 $U$。

$SA \ge SU$，所以 $TA \ge TU$，所以 $TA + TV \ge TU + TV$。因此，可以得知 $AV$ 也是图的一条直径。

危险

该性质的成立前提是边权均为非负。

在情况 1 中，我们使用了 $PV \le TV$，$PU \le TU$。这两个不等式成立的前提是 $PT \ge 0$。负权边会破坏这里的前提。

性质2

提示

直径的两个端点一定是叶子

如果 $A$ 不是叶子，那么除了通向 $B$ 的方向以外还可以继续延伸；由于边权为正，就能得到一条比 $A-B$ 更长的路径，矛盾。

危险

注意边权为正这一点。以及若根节点的度数为 $1$，那么根节点也有可能作为直径的一个端点出现。

性质3

提示

任意点的最远点，一定可以在一条固定直径的两个端点中找到。

设从 $x$ 出发，所能到达的最远点为 $y$。

设 $P$ 是 $x$ 到直径 $A-B$ 的接入点，$Q$ 是 $y$ 到直径 $A-B$ 的接入点。

情况1

$x、y$ 的接入点不同

此时因为 $Qy \le QB$，所以 $xy \le xB$。因此，将 $y$ 换成 $B$，结果不会更差。

情况2

接入点是同一个点，甚至 $x$ 和 $y$ 接入到直径 $AB$ 之前就已经合并。

无论哪种情况，$PB \le Py$，因此，$xB \le xy$。

性质4

定义树上节点 $x$ 的偏心距 $e(x)$ 为从 $x$ 出发，所能到达最远节点的距离。

树的中心是指偏心距最小的节点。

提示

所有直径一定经过树的中心。

性质5

提示

一棵树上，一定存在一个点 $p$ 被这棵树的所有直径经过。

性质6

提示

任意两条直径一定有且仅有一个极长连续段（可以只是一个点）重合。若两条直径共用一个端点，这个端点也算重合。

树形 DP 求树的直径

设树根为 $1$ 号节点，$D[x]$ 表示从节点 $x$ 出发走向以 $x$ 为根的子树，能够到达的最远节点的距离。

设 $x$ 的子节点为 $y_1, y_2, \cdots,$，那么

$D[x] = max\{D[y_i] + e(x, y_i) \}$

设 $F[x]$ 表示子树 $x$ 中，经过 $x$ 的最长链的长度。

那么，以 $x$ 为端点，向其子树出发的链中，选择最长的两条合在一起便是在子树 $x$ 中， 经过 $x$ 的最长链。

因此

$F[x] = max \{ D[y_i] + e(x, y_i) + D[y_j] + e(x, y_j) \}$

在实际实现的过程中，我们没必要分别枚举 $i, j$ 来计算答案。在依次枚举 $x$ 的子节点的过程中，令 $D[x]$ 保存当前所得到的 $D[y] + e(x, y)$ 的最大值，若当前节点为 $y_i$，通过 $y_i$ 所能得到的最长链为 $D[x] + d[y_i] + e(x, y_i)$，经过当前节点以后，$D[x]$ 更新为 $\max \{D[x], D[y] + e(x, y_i) \}$。

void dp(int x) {
    v[x] = 1;
    for (auto [y, z]: e[x]) {
        if (v[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + z);
        d[x] = max(d[x], d[y] + z);
    }
}

两次 BFS 求树的直径

1. 从任意一个节点出发，通过 BFS 或 DFS 对树进行一次遍历，求出与出发点距离最远的节点，记为 $p$。
2. 从节点 $p$ 出发，通过 BFS 或 DFS 对树再进行一次遍历，求出与 $p$ 距离最远的节点，记为 $q$。

从 $p$ 到 $q$ 的路径就是树的一条直径。