企业官网建设流程全解析

这题我在洛谷上刷到的时候，第一反应是“普及+居然把树的直径和离散化凑一块儿了”，心里其实有点犯嘀咕。等我把题面里的故事外壳剥掉，把模型搭出来之后，才明白这题的难点根本不在算法本身，而是你能不能识别出“这题要用树的直径”这个关键信号。整道题做完，我最大的感受是：它其实是一道非常经典的“套路识别 + 基础算法组合”题，树的直径负责解决距离类询问，离散化负责把数据范围压到能开的数组大小，两个东西都不难，但组合起来很考功力。

这篇文章我按自己的完整做题流程来写，从题面解读、算法选型、离散化细节，到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. 树的直径：不只是两条DFS

2.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，因为它不仅能求出直径长度，还能顺便求出直径端点到所有节点的距离数组，这正好是这题后续要用的关键预处理。树形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三件套。代码片段大概是这样的：

vector<int> 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为询问数，注意边数不一定等于节点数 vector<pair<long long, long long>> edges; vector<long 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(); vector<vector<int>> 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时习惯用vector<int> dist(n + 1, -1)做初始化，-1表示未访问过，这样顺带完成了visited标记和距离记录两件事。

vector<int> distA, distB; int endpointA, endpointB; function<void(int, int, vector<int>&)> dfs = [&](int u, int fa, vector<int>& 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 { vector<int> 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 完整代码与复杂度分析

我把上面的片段拼成一个完整可运行的C++17代码，省略输入输出优化以外的杂项：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<pair<long long, long long>> edges; vector<long 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(); vector<vector<int>> 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); } vector<int> dist; function<void(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; vector<int> distA = dist; dist.assign(m + 1, -1); dist[B] = 0; dfs(B, 0); vector<int> 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的递归深度在链状树（一条直线）的情况下会达到n，C++默认递归栈在Windows上往往只有1MB左右，n到2e5就可能直接爆栈。我第一版代码就是在链状数据上RE的。

解决办法有两种：一是直接在编译器指令里加大栈空间（#pragma comment(linker, "/STACK:102400000,102400000")，但这个在Linux OJ上不一定有效）；二是抛弃递归，改成显式栈模拟DFS，或者直接用BFS，反正边权为1，BFS天然适合求距离。我用BFS替换了DFS后再也没出过栈相关的问题。

5.2 unique之后忘了erase

unique只是把重复元素移到容器末尾，并没有改变容器的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变成m+1，访问dist数组直接越界。

我一开始假设查询编号必然合法，结果有一组数据就给我报错。后来我加了一个安全性检查：如果找不到就特判输出一个约定值，或者直接跳过。竞赛里你要么仔细读题确认编号范围，要么就把防御性判断写上。

5.5 常见问题速查表

6. 从这一题延伸出去

6.1 这类题型的迁移套路

“树的直径 + 离散化”这个组合，在比赛里其实经常以变体出现。比如给你一棵树，求“从任意起点出发，最快覆盖全树需要多久”，答案就是树的半径（直径的一半向上取整）；再比如“多次询问某个点到全树最远点的距离”，就是这题的翻版，直接预处理两个端点距离数组后O(1)回答。

还有一种常见变形是把树换成基环树，求“环上任意一点到某点距离”，做法是先处理环再拆成森林，最后在多条链上用树的直径思想。这个难度就上去了，但核心思想一脉相承。

6.2 怎么在考场上识别“这题要用树的直径”

我自己的经验是：题目中出现“最远”“覆盖全部”“最短时间”“两两距离最大”这类表述，且给定的结构是树（无环连通图），就要立刻想到树的直径的可能性。尤其是单起点的扩散问题，如果问的是“从起点出发，最晚被覆盖的节点需要多久”，那第一个要尝试的解法就是用直径端点的距离公式。

多源扩散不要硬套树的直径，那是多源BFS的领域。单源扩散 + 大量询问，才是直径预处理的舒适区。判断清楚是单源还是多源，这非常关键。

6.3 给冲普及+选手的建议

如果你正在准备普及组高分或刚接触提高组，我建议把这题的完整流程亲手敲三遍。第一遍照着代码抄，理解每一行在干什么；第二遍关掉代码自己写，卡住就看关键结论；第三遍尝试换一种建图方式（比如链式前向星）再实现一遍，加深记忆。

树的直径相关的题目，网上已有大量题单，找那种“树的直径 + 距离查询”组合的题去刷。离散化也一样，多找几道需要坐标压缩的题目练手，重点练lower_bound的边界使用。两个技能拆开都不难，但组合起来才是这题真正的价值，以后遇到更复杂的图论题，你会发现这套预处理思路到处都能用上。

我在实际写这题的时候，最大的收获不是背下了树的直径模板，而是学会了“看到单源扩散 + 全树最远时间”就条件反射地想到直径端点，然后把问题拆成预处理和查询两个阶段。这种拆题思路比单题AC重要得多。如果你也把这题彻底吃透了，下次在赛场上碰到类似模型，希望你能比当年的我更快地想到这一步。