刷题群里很多人一看到“树的直径”这名字就直接绕道走觉得又是那种理论味很重的定义。其实把概念撕开它就是一句话在树这种结构里找两个距离最远的节点之间的路径长度。这里说的“距离”通常指路径经过的边数如果是带权树就指边权之和。这个长度也就是这棵树的“最远两点的跨度”。这个题目在算法竞赛、面试手撕代码、甚至一些工程建模里都会冒出来。比如网络拓扑里评估端到端最大延迟、数据链路中找最长跳数、文献里找“离群点”的思路本质上都能抽象成在一棵无向树上求最远点对。更实在的是树的直径是很多树类算法的基础工具求树的重心要它的距离信息做树分治要知道子树的直径合并两颗树时要维护新的直径动态加点的场景里也要维护直径。所以学会这个专题不是背一道板子而是给自己攒下一套能反复移植的思维方式。我见过不少做法有人只会背两次 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 算法流程两次扫描法的思路非常直观就三步从任意一个节点 S 出发做一次 DFS/BFS求出所有点到 S 的距离记距离 S 最远的节点为 A。再从 A 出发做第二次 DFS/BFS求出所有点到 A 的距离。第二次遍历中距离 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; vectorint 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] 1v 往下走的最长链再加上 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; vectorint 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不是 max1max2因为父节点只需要一条向下的链拼接。3.4 两种方法的横评对比对比维度两次扫描法树形 DP时间复杂度O(n)O(n)空间复杂度O(n)O(n)实现简单度更简单模板短稍复杂但也不难负权边支持不支持支持路径还原需要额外记录前驱相对麻烦一些是否能顺便求每个子树直径不能可以从实战角度看纯求直径、边权非负、数据规模又大我一般优先写两次扫描代码量少逻辑清晰。如果题目带负权边或者要求输出所有子树的直径、需要在动态规划过程中维护额外信息那就选树形 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 完成后 vectorint 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 呈现出诡异的随机数。排查方法很简单把数组整体开大一点或者用vectorvectorint 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那遇到稍微绕一点的题照样无从下手。我建议你拿到一棵随机树亲手在纸上标出直径端点再随机选一个起点做两次扫描你就会对“最远端点”这个结论产生肌肉记忆。后面再碰到树相关的复杂题至少能比别人多一个破题口。
