02.树的直径

树上任意两节点之间最长的简单路径即为树的「直径」。

前置知识：树基础。

引入

显然，一棵树可以有多条直径，他们的长度相等。

可以用两次 DFS 或者树形 DP 的方法在 $O(n)$ 时间求出树的直径。

两次 DFS

首先从任意节点 $y$ 开始进行第一次 DFS，到达距离其最远的节点，记为 $z$，然后再从 $z$ 开始做第二次 DFS，到达距离 $z$ 最远的节点，记为 $z^{\prime }$，则 $\delta (z,z^{\prime })$ 即为树的直径。

显然，如果第一次 DFS 到达的节点 $z$ 是直径的一端，那么第二次 DFS 到达的节点 $z^{\prime }$ 一定是直径的一端。我们只需证明在任意情况下，$z$ 必为直径的一端。

定理：在一棵树上，从任意节点 $y$ 开始进行一次 DFS，到达的距离其最远的节点 $z$ 必为直径的一端。

证明

使用反证法。记出发节点为 $y$。设真实的直径是 $\delta (s,t)$，而从 $y$ 进行的第一次 DFS 到达的距离其最远的节点 $z$ 不为 $t$ 或 $s$。共分三种情况：

• 若 $y$ 在 $\delta (s,t)$ 上：

有 $\delta (y,z)>\delta (y,t)⟹\delta (x,z)>\delta (x,t)⟹\delta (s,z)>\delta (s,t)$，与 $\delta (s,t)$ 为树上任意两节点之间最长的简单路径矛盾。

• 若 $y$ 不在 $\delta (s,t)$ 上，且 $\delta (y,z)$ 与 $\delta (s,t)$ 存在重合路径：

有 $\delta (y,z)>\delta (y,t)⟹\delta (x,z)>\delta (x,t)⟹\delta (s,z)>\delta (s,t)$，与 $\delta (s,t)$ 为树上任意两节点之间最长的简单路径矛盾。

• 若 $y$ 不在 $\delta (s,t)$ 上，且 $\delta (y,z)$ 与 $\delta (s,t)$ 不存在重合路径：

有 $\delta (y,z)>\delta (y,t)⟹\delta (x^{\prime },z)>\delta (x^{\prime },t)⟹\delta (x,z)>\delta (x,t)⟹\delta (s,z)>\delta (s,t)$，与 $\delta (s,t)$ 为树上任意两节点之间最长的简单路径矛盾。

综上，三种情况下假设均会产生矛盾，故原定理得证。

负权边

上述证明过程建立在所有路径均不为负的前提下。如果树上存在负权边，则上述证明不成立。故若存在负权边，则无法使用两次 DFS 的方式求解直径。

如果需要求出一条直径上所有的节点，则可以在第二次 DFS 的过程中，记录每个点的前序节点，即可从直径的一端一路向前，遍历直径上所有的节点。

树形 DP

方法 1

指定 $1$ 为树的根，对每个节点 $u$ 维护：

• $d_1[u]$：从 $u$ 向下延伸的最长路径长度
• $d_2[u]$：从 $u$ 向下延伸的次长路径长度（与最长路径无公共边）

核心思想：直径必然经过某个节点 $u$，从 $u$ 向两个不同子树延伸。因此直径 = $\max \{d_1[u]+d_2[u]\}$（对所有节点 $u$ 取最大值）。

树形 DP 可以在存在负权边的情况下求解出树的直径。

如何还原直径路径：

在 DP 过程中额外记录：

• 每个节点 $u$ 的最长路径和次长路径分别通向哪个子节点
• 找到使 $d_1[u]+d_2[u]$ 最大的节点 $u$（直径的”拐点”）
• 从 $u$ 出发，沿着记录的子节点方向分别向两侧走到叶子，即可得到完整直径路径

例如：
       u (拐点)
      / \
     /   \
  子树1  子树2
   |      |
  最长   次长
  路径   路径

方法 2

这里提供一种只使用一个数组进行的树形 DP 方法。

我们定义 $dp[u]$ 为以 $u$ 为根的子树中，从 $u$ 出发的最长路径。那么容易得出转移方程：$dp[u]=\max (dp[u],dp[v]+w(u,v))$，其中的 $v$ 为 $u$ 的子节点，$w(u,v)$ 表示所经过边的权重。

对于树的直径，实际上是可以通过枚举从某个节点出发不同的两条路径相加的最大值求出。因此，在 DP 求解的过程中，我们只需要在更新 $dp[u]$ 之前，计算 $d=\max (d,dp[u]+dp[v]+w(u,v))$ 即可算出直径 $d$。

例题

Luogu B4016 树的直径

给定一棵 $n$ 个节点的树，求其直径的长度。$1\le n\le 10^5$。

两次 DFS 的参考实现

#include <cstdio>
#include <vector>
using namespace std;
 
constexpr int N = 100000 + 10;
 
int n, c, d[N];
vector<int> E[N];
 
void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}
 
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}

使用两个数组的树形 DP 参考实现

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
 
constexpr int N = 100000 + 10;
 
int n, d;
int d1[N], d2[N];
vector<int> E[N];
 
void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
      d2[u] = d1[u], d1[u] = t;
    else if (t > d2[u])
      d2[u] = t;
  }
  d = max(d, d1[u] + d2[u]);
}
 
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}

使用一个数组的树形 DP 参考实现

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
 
constexpr int N = 100000 + 10;
 
int n, d;
int dp[N];
vector<int> E[N];
 
void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    d = max(d, dp[u] + dp[v] + 1);
    dp[u] = max(dp[u], dp[v] + 1);
  }
}
 
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}

性质

树的直径具有如下性质：若树上所有边边权均为正，则树的所有直径中点重合。

证明

证明：使用反证法。设两条中点不重合的直径分别为 $\delta (s,t)$ 与 $\delta (s^{\prime },t^{\prime })$，中点分别为 $x$ 与 $x^{\prime }$。显然，$\delta (s,x)=\delta (x,t)=\delta (s^{\prime },x^{\prime })=\delta (x^{\prime },t^{\prime })$。

有 $\delta (s,t^{\prime })=\delta (s,x)+\delta (x,x^{\prime })+\delta (x^{\prime },t^{\prime })>\delta (s,x)+\delta (x,t)=\delta (s,t)$，与 $\delta (s,t)$ 为树上任意两节点之间最长的简单路径矛盾，故性质得证。

应用场景

树的直径在算法竞赛和实际问题中有多个重要应用：

1. 最小化最大距离问题

在树上选择 $k$ 个点作为 ” 服务中心 “，使得所有点到最近服务中心的最大距离最小。

应用直径的性质：

• 对于 $k=1$：最优位置是直径的中点，使最大距离为 $\lceil \text{直径}/2\rceil$
• 对于 $k=2$：在直径上均匀分布两个点
• 典型例题：消防站选址、服务器部署

2. 树的中心

树的中心：到树上所有点最大距离最小的点

• 树的中心一定在直径上
• 如果直径长度为偶数，中心唯一（直径中点）
• 如果直径长度为奇数，有两个中心（直径中间的两个点）

3. 树的形态分析

判断树的类型：

• 直径 $\approx n-1$：链状树
• 直径 $\approx 2$：星形树
• 直径 $\approx 2\log n$：平衡树

网络拓扑优化：

• 通信网络中，直径反映了最坏情况下的通信延迟
• 希望构建直径较小的网络拓扑

4. 树的覆盖与控制

覆盖问题：

• 用半径为 $r$ 的圆覆盖整棵树（圆心在树上某点）
• 最少需要 $\lceil \text{直径}/(2r)\rceil$ 个圆

控制集问题：

• 在树上选最少的点，使得每个点到选中点的距离 $\le k$
• 需要 $\lceil \text{直径}/(2k+1)\rceil$ 个点

5. 实际问题建模

1. 消防站选址：在树形道路网中建消防站，使得最远的房子到消防站的距离最小（SDOI2011 消防）
2. 网络延迟优化：在服务器网络中，直径代表最坏情况下的请求延迟
3. 供水系统设计：在树形管网中放置水塔，使得最远用户的水压损失最小
4. 生物进化树分析：在系统发育树中，直径反映物种间的最大进化距离

关键性质总结

• 从任意点出发两次 DFS 可求直径，时间复杂度 $O(n)$
• 树的中心在直径上（直径中点或中间两点）
• 所有直径的中点重合（边权为正时）
• 直径提供了树上最长路径的上界
• 直径反映了树的 ” 细长 ” 程度

习题

LeetCode 相关题目

• LeetCode 543. 二叉树的直径 - 基础题，直接应用树形 DP
• LeetCode 1245. 树的直径 - 无根树直径，可用两次 DFS 或树形 DP
• LeetCode 310. 最小高度树 - 找树的中心，与直径相关
• LeetCode 2246. 相邻字符不同的最长路径 - 带约束条件的树直径
• LeetCode 1617. 统计子树中城市之间最大距离 - 子树直径问题

OI/ICPC 题目

• CodeChef, Diameter of Tree
• Educational Codeforces Round 35, Problem F, Tree Destruction
• ZOJ 3820 Building Fire Stations
• CEOI2019/CodeForces 1192B. Dynamic Diameter
• ICPC 2019 上海赛区网络赛 Lightning Routing I
• NOIP2007 提高组 树网的核
• SDOI2011 消防
• APIO2010 巡逻