企业官网建设流程全解析

刷题群里很多人一看到“树的直径”这名字就直接绕道走，觉得又是那种理论味很重的定义。其实把概念撕开，它就是一句话：在树这种结构里，找两个距离最远的节点之间的路径长度。这里说的“距离”，通常指路径经过的边数；如果是带权树，就指边权之和。这个长度也就是这棵树的“最远两点的跨度”。

这个题目在算法竞赛、面试手撕代码、甚至一些工程建模里都会冒出来。比如网络拓扑里评估端到端最大延迟、数据链路中找最长跳数、文献里找“离群点”的思路，本质上都能抽象成在一棵无向树上求最远点对。更实在的是，树的直径是很多树类算法的基础工具：求树的重心要它的距离信息，做树分治要知道子树的直径，合并两颗树时要维护新的直径，动态加点的场景里也要维护直径。所以学会这个专题，不是背一道板子，而是给自己攒下一套能反复移植的思维方式。

我见过不少做法：有人只会背两次 DFS 的模板，遇到“边权有负数”直接崩；也有人只知道树形 DP 的写法，但让他还原具体路径或者处理带权图就卡壳。这篇文章我会把两次扫描和树形 DP 两条路线都拆开，结合代码、正确性理由、边界条件和常见坑位，一步一步给你讲透。

1. 项目概述：树的直径到底在算什么

1.1 先说清楚“树”和“直径”的关系

我们平时说的树，是一个有 n 个节点、n-1 条边的连通无环图。因为无环，所以任意两个节点之间只存在唯一一条简单路径。这个“唯一路径”是树的直径所有算法成立的根本前提——你可以把树理解成一棵真实的树的分支结构，从一个节点到另一个节点，只有一条天然走法，不存在“绕路”这种说法。

树的直径，就是在所有这样的点对路径里，找长度最大的那条。比如一棵链状树，从链头到链尾的距离就是它的直径；一棵星形树，随便两个叶子之间的距离都是 2，直径也就是 2。

这里有一个容易混淆的点：直径是一条具体的路径，而不是一个单点值。虽然题目通常只问你“长度是多少”，但内部实现必须保得住这条路径上的节点。我遇到很多初学者，求出了长度，但让他输出路径上任意一个中间节点，他会愣住。这就是只背结论没理解实现细节的典型症状。

1.2 形式化定义，给自己一个精确坐标

给定一棵无根树 T=(V,E)，定义 d(u,v) 为从 u 到 v 唯一路径的边数之和。树的直径 D 就是：

D = max{ d(u, v) | u, v ∈ V }

如果边有权值 w(e)，就把边数换成权值之和：

D = max{ Σ w(e) 其中 e 在 u 到 v 的唯一路径上 }

注意，无向树没有根的概念，所以任意选一个根都行，这给算法带来了巨大的方便。带权情况下，边权一般要求非负；如果出现负数，两次扫描法会失效，但树形 DP 依然能处理。这一点我在后面会专门展开。

1.3 这个知识点在真实场景里长什么样

先给几个我会拿来当作引子的现实场景，都是树的直径的“马甲”。

第一个是网络评估。一个局域网里的交换机节点可以看成树状拓扑，求“任意两台设备之间的最大跳数”，本质上就是求直径。第二种是社交关系链，群里最强的“转介绍路径”长度，可以用来评估传播的极端深度。第三种是文件依赖分析，把构建任务看成依赖树，最长依赖链就是树的直径，它往往决定了整条流水线的最坏耗时。

工程里的树不一定是二叉的，也不一定严格有序，但这些都不影响算法本身。只要满足连通无环，就可以套用下面的所有方法。

2. 两次扫描法：最简洁也最常用

2.1 算法流程

两次扫描法的思路非常直观，就三步：

1. 从任意一个节点 S 出发，做一次 DFS/BFS，求出所有点到 S 的距离，记距离 S 最远的节点为 A。
2. 再从 A 出发，做第二次 DFS/BFS，求出所有点到 A 的距离。
3. 第二次遍历中，距离 A 最远的节点记为 B，那么 A 到 B 的这条路径就是树的直径。

很多时候题目只问长度，那答案就是 dist[B]。如果要输出路径，就在第二次遍历中记录一下每个点的前驱节点，最后从 B 一路回溯到 A。

2.2 为什么这样两次遍历就能找到最长路径

我坚信一个算法不能只背流程，得知道它为什么对。尤其这个性质，面试官如果追问，答不上来会显得很虚。

先说结论：第一次 DFS 找到的最远点 A，一定会在某条直径的其中一个端点上。这等于说，只要从 A 出发再找一次最远点，得到的路径自然就是全局最长路径。

证明思路用反证法。假设真正的直径是 (X, Y)，距离是 L。第一次从 S 出发找到的最远点是 A，不妨假设 A 既不是 X 也不是 Y。由于树中任意两点的路径唯一，我们可以讨论 S 到 A 的路径与 X 到 Y 的路径之间的关系。如果这两条路径在某个点相交，那么在交点处分叉出去的部分长度会存在矛盾，最终可以推出一条比 L 更长的路径来。如果两条路径完全不相交，又因为一棵树里任意两点之间一定有唯一通路，这通路会把两条路径连起来，继而构造出更长的路径，同样矛盾。

严格证明写起来又长又绕，我建议你先把这个结论当成一条引理记住：从任意节点出发，最远点必是直径端点。这个引理在带非负权边的树上依然成立，但一旦出现负权边，它就不成立了。原因很简单：距离的计算中有负贡献，最远点的选择会受到负数干扰，第一次找出来的 A 未必是直径端点。这种情况下就老老实实换树形 DP。

2.3 无向树上的 DFS 实现

我先把最常用的 C++ 写法给出来。这里用的是邻接表存图。

#include <bits/stdc++.h> using namespace std; const int N = 100005; vector<int> g[N]; int dist[N]; // dfs 统计从 u 出发到其他点的距离 // fa 表示父节点，防止往回走 void dfs(int u, int fa) { for (int v : g[u]) { if (v == fa) continue; dist[v] = dist[u] + 1; dfs(v, u); } } int main() { int n; scanf("%d", &n); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } // 第一次：从任意点出发，找到最远点 A dfs(1, 0); int A = 1; for (int i = 1; i <= n; i++) { if (dist[i] > dist[A]) A = i; } // 第二次：从 A 出发，求到每个点的距离 memset(dist, 0, sizeof(dist)); dfs(A, 0); // 第二次的最远距离就是直径长度 int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, dist[i]); } printf("%d\n", ans); return 0; }

代码里有个关键细节：dfs函数用fa参数记录父节点，避免在无向图里走回头路。这是新手最容易漏掉的。如果不传父节点，v == fa这个判断缺失，DFS 会在两个节点之间来回跳，最后栈溢出。

Python 版本也常用来快速验证小数据，我顺手写一版：

import sys sys.setrecursionlimit(1 << 20) def dfs(u, fa, dist): for v in g[u]: if v == fa: continue dist[v] = dist[u] + 1 dfs(v, u, dist) n = int(sys.stdin.readline()) g = [[] for _ in range(n + 1)] for _ in range(n - 1): u, v = map(int, sys.stdin.readline().split()) g[u].append(v) g[v].append(u) dist = [0] * (n + 1) dfs(1, 0, dist) A = dist.index(max(dist)) dist = [0] * (n + 1) dfs(A, 0, dist) print(max(dist))

这段代码在 n 为 10 万级别时，只要把递归深度限制调大，一般能跑。但如果是 100 万节点的链状树，递归就很可能爆栈。生产环境或者牛客/力扣的部分压测数据，更推荐用 BFS 替代 DFS，或者用显式栈。BFS 代码和 DFS 几乎没有区别，只是把递归换成队列。

2.4 复杂度分析

两次遍历，每次各 O(n)，因为每条边在 DFS 里会被访问一次。空间上，邻接表存边 O(n)，距离数组 O(n)。整体就是 O(n) 时间、O(n) 空间。

对于一棵 n 个节点的树，这个复杂度可以说是理论下界了——你至少得把每条边都看一遍才能确定结构。所以两次扫描法在绝大多数场景下都是最优的选择。

2.5 适用边界，必须注意的两个细节

第一，两次扫描法要求边权非负。前面已经提过，这是正确性证明的基石。如果边权里有负数，第一次找出的“最远点”可能根本不是直径端点，第二次遍历的结果自然就不对了。

第二，如果图不是一棵树，这个方法不能用。比如给的是普通无向图，里面有环，那“唯一路径”的前提就不成立了。你仍然可以尝试暴力求全局最短路，但那就不是 O(n) 能解决的了。考试题目如果明确说“树”，一般没这个烦恼；但有些题会先问一句“这个图是树吗”，你要能反应过来，判连通性+判边数，而不是直接上来跑两遍 DFS。n 个点、n-1 条边且连通，才是树。光满足 n-1 条边但不连通，那是森林，跑两次 DFS 会得到荒谬的结果。

3. 树形 DP：另一种通用解法

3.1 核心状态转移：一个节点能“托起”多长的链

树形 DP 解决直径问题的思路完全不一样。它不再需要“从任意点出发找最远点”的步骤，而是围绕每个节点做局部统计。

定义dp[u]为：从 u 节点出发，往它的子树方向走，能走出的最长链长度。注意这里“链”是一个单方向的路径，只能往下走，不能回头。那么对于节点 u，假设它的每个子节点是 v，子树中的链长度就是dp[v] + 1（v 往下走的最长链再加上 u 到 v 的一条边）。

而经过节点 u 的最长路径，等于它的子节点中，两条最长链拼接在一起。因为树中经过 u 的路径最多只能从两个方向进来：要么从某个子树上来，往下进入另一个子树；要么从子树往下，但根节点 u 作为转折点。所以我们要维护每个节点的“最大链”和“次大链”，两者之和就是“以 u 为转折点的最长路径”。

最后，全局直径就是所有节点的“最大链 + 次大链”里取最大值。

3.2 一个比喻帮你秒懂

想象每个节点是一个平台，从平台出发能垂下去两条绳子，一条最长，一条次长。这个平台能形成的“最长跨距”，就是两条绳子长度之和。而全局答案，就是挑出所有平台里跨距最大的那一个。

这个 DP 的好处在于，它根本不关心根节点选在哪里。不管从哪个节点开始做后序遍历，最终每个节点的最大链和次大链都会被正确统计。而且它对负权边天然免疫——如果最长链是一条负值链，我们完全可以选择不接，权值取 0 就行。

3.3 树形 DP 的代码实现

下面是一份带注释的 C++ 代码。我设定了全局变量ans用来记录答案。

#include <bits/stdc++.h> using namespace std; const int N = 100005; vector<int> g[N]; int ans = 0; int dfs(int u, int fa) { // max1 记录最大链长度，max2 记录次大链长度 int max1 = 0, max2 = 0; for (int v : g[u]) { if (v == fa) continue; int len = dfs(v, u) + 1; // 子树向下延伸长度 + 当前边 if (len > max1) { max2 = max1; max1 = len; } else if (len > max2) { max2 = len; } } // 经过 u 的最长路径，可能是让两条最长链在这里弯折 ans = max(ans, max1 + max2); // 返回给父节点的是 u 往下能走的最长单链 return max1; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); printf("%d\n", ans); return 0; }

代码里有几个容易写错的地方。第一个，ans = max(ans, max1 + max2)必须放在递归完所有子节点之后，因为此时 max1 和 max2 才是完整统计。第二个，初始值 max1、max2 设为 0，隐含了“我可以不要任何子树，直接以当前节点作为一条长度为 0 的链终点”的语义，这对处理负数边权也很关键。第三个，返回值是 max1，不是 max1+max2，因为父节点只需要一条向下的链拼接。

3.4 两种方法的横评对比

从实战角度看，纯求直径、边权非负、数据规模又大，我一般优先写两次扫描，代码量少，逻辑清晰。如果题目带负权边，或者要求输出所有子树的直径、需要在动态规划过程中维护额外信息，那就选树形 DP。另外在面试场景，如果面试官要求“不能用图遍历以外的技巧”，树形 DP 常常被视为标准解，因为它不需要那一条额外证明“最远点是直径端点”的引理，推起来更透明。

4. 进阶确认真经：带权直径与路径还原

4.1 带权树的直径：把边数换成边权

当树的边带权时，两次扫描法的流程不变，唯一改动是dist[v] = dist[u] + w(u,v)。前提是边权必须非负。这里我建议把距离数组类型改成long long，因为权值很大时，一条长链上的累计权值很容易超过 int 上限。我就吃过这个亏，一个链状数据加出的权值直接溢出，答案变成负数，调试了半小时才发现是类型问题。

修改后的核心代码片段如下：

long long dist[N]; void dfs(int u, int fa, long long cur) { dist[u] = cur; for (auto [v, w] : g[u]) { if (v == fa) continue; dfs(v, u, cur + w); } }

4.2 点权直径：把点权折算到边权

有些题目的路径距离是“经过的所有节点的权值之和”，而不是边权。这时候有一个常见的转换技巧：把节点 u 的点权 value[u] 转移到它的父边上。

具体做法：对每条边 (u, v)，把 u 到 v 的边权定义为 value[v]；同时，路径两个端点都要算入权值，所以最终距离要减去一个 value[起点] 或加上一个 value[终点] 之类的偏移。更通行的做法是，用树形 DP 直接统计：

对每个节点 u，在递归时记录dp[u] = max( dp[child] + value[child] , 0 )，也就是从 u 往下走能获取的最大点权和，当前节点的点权在返回时或者拼接时统一处理。这里的细节因题而异，我给个建议：拿到点权题，先把问题手工在草稿纸上走一遍，明确起点和终点的权值要不要计入，再动手写代码。这个“要不要计入”的标记，很多人漏掉之后对着样例对了半天也调不出错。

4.3 输出直径的完整路径

求长度只是第一步，很多题要求把直径上的节点打印出来。用两次扫描法做路径还原非常自然：在第二次 DFS 时记录pre[v] = u，表示 v 的前一个节点。第二次结束后，从最远点 B 开始，不断向前跳，直到碰到 A，把沿途节点收集到数组里，再反转输出。

int pre[N]; void dfs(int u, int fa) { for (int v : g[u]) { if (v == fa) continue; pre[v] = u; dist[v] = dist[u] + 1; dfs(v, u); } } // 主函数中第二次 dfs 完成后 vector<int> path; int cur = B; while (cur != A) { path.push_back(cur); cur = pre[cur]; } path.push_back(A); reverse(path.begin(), path.end());

如果是树形 DP，想输出路径稍微绕一点。需要在递归时额外维护“最大链来自哪个子节点”“次大链来自哪个子节点”，并且在更新答案时记录两条链的端点。我建议，除非题目明确要求输出路径，否则用两次扫描法还原路径是更省事的方案。

5. 扩展应用：树的直径只是起点

5.1 树半径与树中心：直径的“另一半”

有了直径，树的一些相关指标就很容易推出来。比如树的半径，定义为所有节点到最远点的距离中的最小值，可以简单理解成“树的中心到最远叶子的距离”。如果直径长度为 D，那么半径通常就是ceil(D/2)或者D/2，取决于直径长度的奇偶性和边权类型。

找树中心，也就是让“最大距离”最小的那个节点，方法是取直径的中点。在无权树中，如果直径长度为偶数，中心就是正中间那个节点；如果为奇数，中心就是中间两个节点中的任意一个。树中心在很多网络设计题里有实际用途，比如选择部署缓存的位置，让整体最远访问延迟最低。

5.2 两棵树合并后的直径

这个扩展在虚拟树、动态树题里非常常见。假设你有两棵树 T1 和 T2，直径分别是 d1 和 d2，现在用一条边连接 T1 的某个节点 x 和 T2 的某个节点 y，形成新树。问新树的直径是多少？

答案是：

新直径 = max(d1, d2, max( dist_T1(x, a1), dist_T1(x, b1) ) + 1 + max( dist_T2(y, a2), dist_T2(y, b2) ))

其中 a1、b1 是 T1 的直径两个端点，a2、b2 是 T2 的直径两个端点。理由很简单：新直径要么还在原某棵树内部，要么穿过连接边 x-y，那它必然由“x 在 T1 中最远的点”和“y 在 T2 中最远的点”拼接而成。利用直径端点的性质，T1 里离 x 最远的点一定是 a1 或 b1 中的一个，T2 同理。

这个公式在很多“两棵树之间连一条边，问最小最大距离”的题目里会用到。我建议把这条结论存进自己的算法笔记里，它在多个专题里反复被借用。

5.3 动态加点时维护直径

如果系统里不断有新叶节点加入，树的结构在变化，每次重算直径太浪费。维护方法核心还是直径端点的性质：每次加入新节点 x 时，维护当前直径两个端点 A、B。若新端点 candidate 是与 x 相关的一个另一端，只需要把 x 与 A、B 分别算距离，如果dist(x, A)或dist(x, B)大于当前直径长度，就更新 A 或 B。这一套 O(log n) 甚至 O(1)（如果预处理了每个节点的深度和 LCA）就能维护。

同样，如果动态删边或删叶子，问题会更复杂，常和并查集、逆序处理结合。但追根溯源，里面的核心依然是对“直径端点”的理解。

5.4 直径在树分治中的角色

树分治，比如点分治，需要把问题规模递归地“切成”大约一半的子树。找树的重心是关键步骤，而重心和直径存在紧密关系：树的重心一定位于直径上，且到直径两端的距离差不超过 1。因此求完直径后，可以沿着直径方向快速找到重心，比再跑一遍“子树最大规模最小化”的贪心要快不少。

所以很多写过树分治的老手，看到题的第一步就是顺手把直径求了，数据结构准备好了，后面一切顺畅。

6. 常见问题与排查技巧

6.1 递归爆栈：树的深度可不讲道理

一台比赛机器的栈限制往往在 8MB 上下，递归深度超过 10 万就很容易爆栈。如果输入是一条 20 万节点的链，朴素的递归 DFS 直接程序崩溃。解法有三：

第一，在本地调试时，用#pragma comment(linker, "/STACK:1024000000,1024000000")这种编译器指令扩展栈（仅限部分环境）。第二，把递归改成显式栈，就是自己在代码里维护一个 vector 模拟栈。第三，用 BFS 代替 DFS，因为 BFS 本身没有递归栈问题。对于必须要 DFS 的题目，建议优先 BFS 求距离，或者用迭代加深等技巧规避暴栈风险。

6.2 邻接表空间与下标问题

无向树每条边要存两次。如果题目节点编号从 1 到 n，邻接表建议开n + 1个数组。我见过最典型的新手错误是这样的：开了一个大小为 n 的数组，节点编号却是从 1 开始的，任何访问都会数组越界。在很多在线评测环境里，越界不一定报错，它只会静默地踩坏内存，让你后面算出来的 dist 呈现出诡异的随机数。排查方法很简单：把数组整体开大一点，或者用vector<vector<int>> g(n + 1)这种动态结构，不用手动管大小。

6.3 多组测试数据没有重置

一道题如果有 T 组数据，dist数组和全局ans必须在每组开头重置。这个坑非常隐蔽，尤其是ans，如果上一组数据已经更新成很大值，这组数据全是小树，你的答案可能直接沿用旧值，导致连续 WA。我自己的习惯是：写多组数据时，把“初始化”放在最醒目的位置，并在本地用多组数据测试覆盖。

6.4 用暴力算法做交叉验证

当你不确定自己写的是不是对时，最好的办法不是去查题解，而是写一个 O(n^2) 的暴力版本来做小规模随机对拍。

思路很简单：对 n 不超过 10 的小树，枚举所有点对，每次 BFS 求距离，记录最大值。然后随机生成 100 棵小树，分别跑暴力算法和你的优化算法，对比结果是否一致。我提供一个 Python 验证脚本的思路：

import random from collections import deque def brute(n, g): ans = 0 for s in range(n): dist = [-1] * n q = deque([s]) dist[s] = 0 while q: u = q.popleft() for v in g[u]: if dist[v] == -1: dist[v] = dist[u] + 1 q.append(v) ans = max(ans, max(dist)) return ans def solve(n, g): # 这里放你的两次 BFS 实现 pass for _ in range(100): n = random.randint(2, 10) g = [[] for _ in range(n)] for i in range(1, n): p = random.randint(0, i - 1) g[i].append(p) g[p].append(i) if brute(n, g) != solve(n, g): print("Wrong") break

这种对拍习惯，远比看半天别人代码有效。它能让你在几分钟内建立对自己实现的信心，同时逼你理解自己的每一步在做什么。

6.5 直径长度非唯一的点

注意，树的直径可能不止一条。两个点对可能共享同一条长度，但路径不同。题目如果没有特别说明，一般只需要输出长度，不需要输出具体哪一条。如果题目要求输出字典序最小的直径路径，或者特定限制条件的直径，那就需要在求长度之外维护附加信息。此时树形 DP 往往更好扩展，因为可以在ans = max(ans, max1 + max2)时同步比较字典序。

我个人在实际操作中的体会是，树的直径这个题目，考的根本不是背模板，而是你能不能把“第一次找到最远点，第二次从最远点再走一遍”的性质，移植到各种变形场景。尤其是合并树、动态维护直径、边权带权、点权转换这些扩展，它们都指向同一套底层思维：树的路径唯一性 + 直径端点的特殊地位。

如果你只是会抄两遍 DFS，那遇到稍微绕一点的题，照样无从下手。我建议你拿到一棵随机树，亲手在纸上标出直径端点，再随机选一个起点做两次扫描，你就会对“最远端点”这个结论产生肌肉记忆。后面再碰到树相关的复杂题，至少能比别人多一个破题口。