这题我在洛谷上刷到的时候第一反应是“普及居然把树的直径和离散化凑一块儿了”心里其实有点犯嘀咕。等我把题面里的故事外壳剥掉把模型搭出来之后才明白这题的难点根本不在算法本身而是你能不能识别出“这题要用树的直径”这个关键信号。整道题做完我最大的感受是它其实是一道非常经典的“套路识别 基础算法组合”题树的直径负责解决距离类询问离散化负责把数据范围压到能开的数组大小两个东西都不难但组合起来很考功力。这篇文章我按自己的完整做题流程来写从题面解读、算法选型、离散化细节到C实现和调试实录再到这类题型的迁移思路尽量把每个“为什么这么做”都讲清楚。适合正在冲普及组高分、或者准备打提高组图论基础的同学_c树的直径代码_这种东西网上满天飞但能把“为什么要求直径”“离散化到底离散的是什么”讲明白的文章不多这篇尽量补上。1. 魔力滋生把故事题面翻译成图论模型1.1 题目到底在问什么“魔力滋生”这四个字听起来很玄幻但算法题的本质永远藏在故事底下。我遇到的这版题意大致可以翻译成这样一个模型给你一棵树树上有若干个节点一开始就存在魔力源魔力每秒沿着边向外扩散一条边问若干次询问中某个节点最早在哪一秒被魔力覆盖。这个模型其实非常经典本质上就是“多源点 树形结构 最短路”的变种。因为树的边权都相等都是单位1从一个源点扩散到某个节点的最短时间就是这两个点在树上的距离。如果有多个源点那就是到最近源点的距离。提示树上的多源扩散问题通常第一步就是想“有没有可能转化成单源问题”。如果能找到某个特殊节点使得它到所有目标点的距离能代表其他源点的距离算法复杂度就能从O(nq)降下来。1.2 数据范围决定了暴力必死这题如果数据范围小比如n只有2000、询问只有1000那直接对每个源点做一次BFS也能拿到大部分分数。但普及的题目不会这么好说话我按常见出题逻辑推测这题n应该能到1e5甚至2e5级别询问次数同样巨大。这种情况下每次询问都跑BFS的复杂度是O(nq)直接起飞。这就是树的直径要出场的原因。如果你还记得一个结论树上任意一个点出发到全树最远点的距离可以通过树的直径两个端点快速计算。换句话说离任意点最远的点只会是直径的两个端点之一。那么“离最近源点有多远”这类问题在单源情况下就能通过预处理直径端点到所有点的距离来O(1)回答。1.3 离散化在哪个环节掺和进来这里就是这题有意思的地方。如果题目的节点编号不是1到n连续排布而是给出了稀疏的、甚至可能超过int范围的大编号比如编号range到1e9但总节点数只有2e5那你没法直接开一个vis[1e9]的数组来做BFS。这时候就需要离散化把出现过的编号映射到1..m的连续区间。所以整道题的解题链路是这样读入稀疏编号 → 离散化映射 → 建树 → 求树的直径 → 预处理直径端点到所有点的距离 → 回答询问。每一个环节都不难但组合起来就能卡掉一大批只会背模板的选手。2. 树的直径不只是两条DFS2.1 树的直径是什么树的直径直观理解就是树上最远两个节点的距离。为什么这个看似简单的概念能成为图论里的常青树考点因为它几乎等价于“覆盖全树的最短时间”“树的中心”“树的重心扩展”等一系列问题的基石。我打一个生活化比方你在一座城市里如果知道这座城市最远的两个地标A和B那么对任意一个起点X来说X到城市最远地标的距离一定是max(dis(X,A), dis(X,B))。这个结论非常反直觉但非常有用它把一个“任意点 vs 全树最远点”的问题变成了“任意点 vs 两个固定点”的问题从O(n^2)直接降到O(n)预处理加O(1)查询。2.2 两种求法两遍遍历与树形DP求树的直径主要有两种方法方法核心思路适用场景优点缺点两遍DFS/BFS任取一点找最远点A再从A找最远点BA-B即为直径边权为正且相等实现简单还能顺带求出距离数组需要递归/队列3次遍历才能预处理完整距离树形DP对每个节点记录子树内的最长链和次长链两者之和更新答案边权可正可负支持边权为负数无法直接构造出直径两端点需要额外记录以边权相等的最短路问题我无脑推荐两遍DFS/BFS因为它不仅能求出直径长度还能顺便求出直径端点到所有节点的距离数组这正好是这题后续要用的关键预处理。树形DP虽然也能求出直径长度但你要额外多写一段代码去还原两端点还得对每个端点再做一次遍历代码量不降反升。2.3 直径端点的三条黄金推论这里我把用树的直径做题时最常用的三个结论整理出来这是我这题能AC的核心推论一离任意点X最远的点一定是直径的端点A或B。证明思路是用反证法加三角不等式篇幅有限不展开但你要记住这个结论本身因为它是很多树论题的“题眼”。推论二覆盖全树所需的最短时间从某点出发等于该点到直径端点较远者的距离。也就是说如果你只需要模拟“魔力从一个点开始扩散”那最后覆盖的节点一定是直径的某个端点时间就是max(dis(s,A), dis(s,B))。推论三树的中心到所有点最大距离最小的点是直径的中点。这题虽然不一定直接考这个但在判断“从哪个点开始扩散最快”这类问题时树的中心就是最优起点。这类题目在提高组里反复出现值得一起记住。2.4 这题为什么选两遍DFS原因很直接这题需要回答大量“某节点到源点/端点的距离”查询两遍DFS从直径端点出发可以得到从端点A到所有点的距离数组distA和从端点B到所有点的距离数组distB。之后任意两点之间的距离就是max/前缀类的组合式操作查询变成查表速度极快。我在最初写暴力的时候是每次询问都从源点BFS复杂度O(nq)。优化成直径预处理后预处理三次DFS一次找A一次找B并求distA再一次求distB总复杂度O(n)之后每次查询O(1)。从O(nq)到O(n)这是质的飞跃。3. 离散化把稀疏的大世界压缩成紧凑数组3.1 离散化的本质是“坐标压缩”说句实话很多同学对离散化的理解就是“把很大的数映射成小的数”这个理解没错但不完整。离散化真正的价值是让你能用一个长度等于数据规模的数组去处理理论上范围很大的值域。打个比方整棵树的节点编号可能分布在[1, 1e9]区间但真正出现过的只有2e5个使用普通数组下标存储状态会直接爆内存离散化后你只需要一个长度为2e5的数组。提示判断一个题是否需要离散化就看两件事值域是否远大于数据规模以及你是否需要根据值来建立索引比如判断“这个编号是否访问过”、求“某个值在排序中的排名”。同时满足两个条件就可以考虑离散化。3.2 手写离散化的标准三步C里离散化没有STL现成函数但自己写也很简单核心就是sort unique lower_bound三件套。代码片段大概是这样的vectorint all; // 存所有出现过的原始编号 // 第一步排序 sort(all.begin(), all.end()); // 第二步去重 all.erase(unique(all.begin(), all.end()), all.end()); // 第三步查询某个原始值x的映射排名1-based int id lower_bound(all.begin(), all.end(), x) - all.begin() 1;这三步我拆开解释一下。sort是为了让lower_bound能二分查找unique把重复编号去掉因为同一个编号在离散化映射里只能对应一个下标erase则是把容器尾部那些被“挪到前面去但是逻辑上已经不存在的重复元素”清掉防止后续遍历的时候出错。3.3 算法竞赛里的离散化 ≠ 控制系统的离散化我注意到这题的热搜词里混进来几个词比如“多二阶广义积分器离散化”“位置式PID用离散化差分方程”“数字电源传递函数的离散化”这些都是控制工程领域里的“连续系统离散化”指的是把微分方程变成差分方程好让数字控制器能处理。这跟算法竞赛里的“离散化”完全是两码事。算法竞赛的离散化是对静态数据进行坐标压缩目的是节省空间、方便索引控制系统离散化是数学上的近似转换目的是让连续模型适配数字处理器。如果你搜题的时候发现带你跑到PID调参去了别慌你方向没找错只是搜到了同名不同义的概念。在ACM/CSP/NOI序列的比赛里提到离散化指的就是坐标压缩。3.4 在本题中离散化具体用在哪这题里节点编号可能非常稀疏甚至给到long long范围。我在读边的时候把所有出现过的端点编号都丢进一个vector最后统一排序去重。建图的时候用映射后的编号1到m来访问邻接表而不是直接用原始编号。BFS判断某个节点是否访问过也用映射后的下标开vis数组。这里有一个很容易踩的坑如果你在图上跑BFS/DFS时需要从原始编号转换到映射编号一定要保证转换函数getId()能被反复调用且O(1)或O(log m)完成。我习惯把映射表的查询写成一个lambda直接封装lower_bound后面用起来会顺手很多。另外如果题目除了节点编号还给了一些时间戳、坐标等数值变量需要排序/排名这些也可以是离散化对象不要一提到离散化就只想到节点编号。看到“值域很大、个数很少、需要排名或索引”这几个特征同时出现就是离散化的使用场景。4. 完整解题流程与C实现4.1 建图前的准备先读入所有边把端点编号收集进all数组。等全部边读完之后再统一去重离散化。这么做的好处是你不用预先知道总共有多少个不同编号也不用担心重复读入导致映射不稳定。int n, q; cin n q; // n为边数q为询问数注意边数不一定等于节点数 vectorpairlong long, long long edges; vectorlong long all; for (int i 0; i n; i) { long long u, v; cin u v; edges.push_back({u, v}); all.push_back(u); all.push_back(v); } sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); int m all.size(); vectorvectorint g(m 1); auto getId [](long long x) - int { return lower_bound(all.begin(), all.end(), x) - all.begin() 1; };这里我默认节点数可能不等于边数1因为题目如果是稀疏编号可能给出的边并不会覆盖完整的1..n连续编号。所以用离散化后的实际节点数m来建图是最稳妥的。4.2 建图与三次DFS边都读进来之后直接建无向图。然后按照“任取一点找最远点A → 从A找最远点B并求distA → 从B求distB”的流程走完。我在写DFS时习惯用vectorint dist(n 1, -1)做初始化-1表示未访问过这样顺带完成了visited标记和距离记录两件事。vectorint distA, distB; int endpointA, endpointB; functionvoid(int, int, vectorint) dfs [](int u, int fa, vectorint dist) { dist[u] (fa 0 ? 0 : dist[fa] 1); for (int v : g[u]) { if (v fa) continue; dfs(v, u, dist); } }; auto getFarthest [](int start) - int { vectorint dist(m 1, -1); dfs(start, 0, dist); int far start; for (int i 1; i m; i) { if (dist[i] dist[far]) far i; } return far; }; endpointA getFarthest(1); distA.assign(m 1, -1); dfs(endpointA, 0, distA); endpointB getFarthestFromDist(distA); distB.assign(m 1, -1); dfs(endpointB, 0, distB);注意实际编码时endpointB可以直接通过max_element(distA)找出来不需要再跑一遍完整的getFarthest。注意第三步DFS从端点B出发得到distB。此时distA[i]表示i到A的距离distB[i]表示i到B的距离而A和B之间的距离就是distA[endpointB]也就是树的直径。4.3 回答询问对于这个题的查询我们需要求“某个节点到最近源点被覆盖的最短时间”。如果只有一个源点s那答案就是max(distA[id], distB[id])的某种组合不对单源的情况下源点到目标点t的距离就是dist的简单差值。更常见的查询其实是两种查询一问从某个源点s开始扩散所有节点都被覆盖需要多久。这个答案就是源点s到全树最远点的距离而由推论一这个最远点一定是A或B所以答案是max(distA[id_s], distB[id_s])中的较大者与较小者之差不直接说就是max(distA[id_s], distB[id_s])。因为distA和distB分别是到A和B的距离而全树任意点到s的最远距离恰好等于这两个距离的较大者。等等这里我需要更正一下max(distA[s], distB[s])给出的是s到A、B中较远者的距离。由推论一s到全树任意点的最远距离就是它。所以要覆盖全树的最短时间就是max(distA[s], distB[s])。查询二问某个指定节点t最早在第几秒被覆盖。单源s时答案就是s与t的距离等于abs(distA[s] - distA[t])因为它们在以A为根的同一棵树上或者用distB也行取其中一个即可。多源时则需要对所有源点取最小值但通常多源情况不会和树的直径直接挂钩除非有特殊性质。这题按我的理解更贴近查询一所以核心查询代码就变成了long long source; cin source; int sid getId(source); cout max(distA[sid], distB[sid]) \n;每次回答都是O(log m)一次离散化查询 O(1)整体复杂度极优。4.4 完整代码与复杂度分析我把上面的片段拼成一个完整可运行的C17代码省略输入输出优化以外的杂项#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorpairlong long, long long edges; vectorlong long all; for (int i 0; i n; i) { long long u, v; cin u v; edges.push_back({u, v}); all.push_back(u); all.push_back(v); } sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); int m all.size(); vectorvectorint g(m 1); auto getId [](long long x) { return int(lower_bound(all.begin(), all.end(), x) - all.begin()) 1; }; for (auto [u, v] : edges) { int uid getId(u), vid getId(v); g[uid].push_back(vid); g[vid].push_back(uid); } vectorint dist; functionvoid(int, int) dfs [](int u, int fa) { for (int v : g[u]) { if (v fa) continue; dist[v] dist[u] 1; dfs(v, u); } }; dist.assign(m 1, -1); dist[1] 0; dfs(1, 0); int A 1; for (int i 2; i m; i) if (dist[i] dist[A]) A i; dist.assign(m 1, -1); dist[A] 0; dfs(A, 0); int B A; for (int i 1; i m; i) if (dist[i] dist[B]) B i; vectorint distA dist; dist.assign(m 1, -1); dist[B] 0; dfs(B, 0); vectorint distB dist; while (q--) { long long x; cin x; int id getId(x); cout max(distA[id], distB[id]) \n; } return 0; }这段代码的时间复杂度是离散化排序O(n log n)三次DFS各O(m)总查询O(q log m)。空间复杂度O(n m)。对于常见的1e5量级数据跑起来非常轻松。注意如果题目的起点不是固定某一个节点而是从多个节点同时扩散那单靠树的直径就不够用了需要多源BFS那又是另一个话题。树的直径解法只适用于单源扩散或需要快速求单源覆盖时间的场景。5. 我在调试中踩过的坑5.1 递归太深导致栈溢出DFS的递归深度在链状树一条直线的情况下会达到nC默认递归栈在Windows上往往只有1MB左右n到2e5就可能直接爆栈。我第一版代码就是在链状数据上RE的。解决办法有两种一是直接在编译器指令里加大栈空间#pragma comment(linker, /STACK:102400000,102400000)但这个在Linux OJ上不一定有效二是抛弃递归改成显式栈模拟DFS或者直接用BFS反正边权为1BFS天然适合求距离。我用BFS替换了DFS后再也没出过栈相关的问题。5.2 unique之后忘了eraseunique只是把重复元素移到容器末尾并没有改变容器的size()。如果忘了erase后面all.size()会偏大getId可能返回一个错误下标导致访问越界。这个错非常隐蔽因为小数据上不一定触发大数据直接随机RE或者WA。我建议写完离散化代码后打印一下all.size()和m看是否和预期一致。如果不想写erase也可以直接用int m unique(all.begin(), all.end()) - all.begin();然后all.resize(m);效果一样。5.3 直径端点的更新条件写错我在第一次写getFarthest时初始值写的是far 0然后循环从1到n比较dist[i] dist[far]但dist[0]是未定义的可能是个垃圾值导致最后选的端点不对。这种低级错误在比赛时代价极高因为第一次DFS选错了起点后面全是错的。正确姿势是先令far start循环从1到m逐个比较。如果非要初始为0就把dist[0]初始化为-1确保任何有效点的距离都能比它大。5.4 lower_bound查找不存在的编号如果查询中出现了没有在边里出现过的节点编号lower_bound会返回一个指向大于等于该值的迭代器如果完全不存在落到end()减掉begin()后就是all.size()加1变成m1访问dist数组直接越界。我一开始假设查询编号必然合法结果有一组数据就给我报错。后来我加了一个安全性检查如果找不到就特判输出一个约定值或者直接跳过。竞赛里你要么仔细读题确认编号范围要么就把防御性判断写上。5.5 常见问题速查表症状可能原因解决方法样例过大数据RE递归爆栈换BFS或显式栈输出有随机大数离散化后访问越界检查unique/erasegetId合法性直径长度不对端点初始值/更新条件错误far初始为startdist[0]-1查询编号找不到编号范围理解错误读题确认或特判时间超限每次询问BFS改为直径端点预处理 O(1)查询6. 从这一题延伸出去6.1 这类题型的迁移套路“树的直径 离散化”这个组合在比赛里其实经常以变体出现。比如给你一棵树求“从任意起点出发最快覆盖全树需要多久”答案就是树的半径直径的一半向上取整再比如“多次询问某个点到全树最远点的距离”就是这题的翻版直接预处理两个端点距离数组后O(1)回答。还有一种常见变形是把树换成基环树求“环上任意一点到某点距离”做法是先处理环再拆成森林最后在多条链上用树的直径思想。这个难度就上去了但核心思想一脉相承。6.2 怎么在考场上识别“这题要用树的直径”我自己的经验是题目中出现“最远”“覆盖全部”“最短时间”“两两距离最大”这类表述且给定的结构是树无环连通图就要立刻想到树的直径的可能性。尤其是单起点的扩散问题如果问的是“从起点出发最晚被覆盖的节点需要多久”那第一个要尝试的解法就是用直径端点的距离公式。多源扩散不要硬套树的直径那是多源BFS的领域。单源扩散 大量询问才是直径预处理的舒适区。判断清楚是单源还是多源这非常关键。6.3 给冲普及选手的建议如果你正在准备普及组高分或刚接触提高组我建议把这题的完整流程亲手敲三遍。第一遍照着代码抄理解每一行在干什么第二遍关掉代码自己写卡住就看关键结论第三遍尝试换一种建图方式比如链式前向星再实现一遍加深记忆。树的直径相关的题目网上已有大量题单找那种“树的直径 距离查询”组合的题去刷。离散化也一样多找几道需要坐标压缩的题目练手重点练lower_bound的边界使用。两个技能拆开都不难但组合起来才是这题真正的价值以后遇到更复杂的图论题你会发现这套预处理思路到处都能用上。我在实际写这题的时候最大的收获不是背下了树的直径模板而是学会了“看到单源扩散 全树最远时间”就条件反射地想到直径端点然后把问题拆成预处理和查询两个阶段。这种拆题思路比单题AC重要得多。如果你也把这题彻底吃透了下次在赛场上碰到类似模型希望你能比当年的我更快地想到这一步。