P7807“魔力滋生”这道题我在洛谷上刷到的时候第一反应是这题面包装得够狠。一堆魔法水晶、魔力波纹、向周围滋生的设定读下来基本晕乎乎的。但刷了几年树形图论题之后我养成了一个习惯就是先把题面的故事皮撕掉抓住真正的数据结构模型。这道题剥完之后核心就两个词树的直径离散化。难度标着普及并不是因为它本身难到天上去了而是因为这两个模型你得同时拿得出手外加一点点分析能力。这篇文章适合正在学图论基础、树相关算法的同学特别是那种“样例能过、交上去就WA”的选手。它会帮你把BFS、DFS、树的最长路径、数据压缩这些基本功串起来。下面我把完整的拆题思路、两种主流求直径的方法、离散化的标准写法以及我提交过程中踩过的坑一次性讲清楚。1. 真正读题P7807魔力滋生到底在考什么1.1 剥掉故事外衣核心模型只有两个这次题目的描述围绕“魔力滋生”展开有若干个位置位置之间有魔力通道魔力从某个源头开始滋生沿着通道扩散问某种条件下最远能滋到哪或者要统计某个等级的量。这种包装在竞赛里太常见了我每次看到“传播”“蔓延”“感染”“滋生”这类词第一反应就是图上的最远距离或者连通性问题。进一步看如果位置之间连接起来恰好是一棵树也就是N个节点、N-1条边并且全连通那么任意两个位置之间只有唯一一条路径。这时候“最远滋生的距离”就等同于“树上最远的两个节点之间的距离”这个距离就是树的直径。另一件关键事是“离散化”。题目里节点可能不是从1到N紧凑编号或者每个节点带有一个魔力等级等级数值范围很大但实际出现的等级种类却很少。这时候你需要把离散的大数值压缩成连续的序号。为什么必须做这一步因为后面可能要按等级建索引、开数组统计或者按某种顺序处理。数值范围如果到1e9你根本开不了这么大的数组直接拿map去存又容易在时限边缘挣扎。离散化就是以log级别的代价把值域压缩到N级别。所以这道题拆开就是读入一棵树可能带权值属性先建图然后用两遍BFS或DFS求直径。如果答案用到的属性值范围过大就让离散化先上场。最后按题意输出。听起来简单实际上不少人死在了“看着像树的题不敢用树结论”以及“离散化之后下标越界”这些地方。1.2 难度定位与前置知识普及在洛谷对应的大概是CSP-J/S提高组二轮中间那一档比纯模板题高一点又没有到省选那种劝退程度。它考的是基本功是不是扎实一般体现在这几个地方图到底是有向还是无向边权是不是1节点范围有多大数组开得够不够大空图、单点这类的边界情况有没有处理牵扯到的前置知识其实不多但每样都得熟练vector建图或者链式前向星BFS队列求最短路边权为1时DFS递归遍历树离散化三件套sort、unique、lower_bound如果你刚才还觉得这题很难看到这个清单心里应该踏实不少。它没有一个知识点是冷门的关键是怎么把两三个基础工具组合起来选对顺序别在细节上翻车。2. 树的直径为什么第一眼就该想到它2.1 从“魔力传播”到最长路径的思维转换“滋生”这个词在我脑内自动翻译成“扩散”。魔力从一个起点向外扩散问覆盖范围或者最大距离本质就是个距离问题。在树上任意点到任意点的距离等于经过边的条数前提是每条边长度一样最远的一对点之间的距离就是树的直径。为什么要求直径因为很多题目最后要的答案要么直接是直径长度要么和直径的端点有关。比如这一题按常见套路理解是输出直径长度或者沿直径路径上某种属性值之和。无论哪种你都必须先把直径找出来。举个例子你就懂了在一棵树形的社区里假设你要在某个路口装一个广播站想知道声音能不能覆盖到最偏远的住户那你需要知道从广播站到最远住户的距离。进一步如果你想在整棵树里选两个点让它们之间的“连接成本”最大那就要找到这棵树的“最长轴”也就是直径。树的直径就是整棵树里最远的两个点之间的距离。2.2 两遍BFS求直径的原理与实现求树的直径最经典的方法是两遍BFS或DFS。套路非常简单从任意点s出发做一次BFS找到距离s最远的点a。从a出发再做一次BFS找到距离a最远的点b。这时候a和b之间的距离就是树的直径。这个结论成立的原因需要稍微证明一下。任取一点ss到最远点a的路径上必然会碰到某条直径。可以反证说明如果a不是任何直径的端点那么从a能找到更远的点就会推出存在比当前直径更长的路径矛盾。所以第一次BFS找到的a一定是某条直径的端点从a再BFS一次找到的b就是直径的另一端。这个结论在无根树上普遍成立而且只要边权为1BFS天然就是求最短路的工具。实现方面我习惯用BFS原因很实在队列迭代没有递归爆栈的风险尤其是树链很长的时候边权为1BFS天然求出最短距离代码简洁调试容易下面是核心函数。第一次调用它返回最远点第二次调用它返回另一个端点并且dist数组里记录的就是从起点到各点的距离const int MAXN 200005; vectorint g[MAXN]; int dist[MAXN]; int bfs(int s) { queueint q; memset(dist, -1, sizeof(dist)); q.push(s); dist[s] 0; int far s; while (!q.empty()) { int u q.front(); q.pop(); if (dist[u] dist[far]) { far u; } for (int v : g[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } return far; }调用方式int a bfs(1); int b bfs(a); int diameter dist[b];注意一下第二次BFS内部会重新memset掉dist所以第一次BFS的结果只有a保留下来了。第二次BFS结束后dist[b]就是从a到全图最远点的距离它就是直径长度。2.3 树形DP求直径的备选方案两遍BFS是无权树求直径最顺手的办法但如果题目边权不是1或者你不想写两个函数树形DP也能一遍算完。思想是以任意一点为根做DFS设dp[u]表示以u为根的子树中从u出发往子树内部走能走到的最远距离。对每个儿子vint ans 0; void dfs(int u, int fa) { for (int v : g[u]) { if (v fa) { continue; } dfs(v, u); // 用经过u的两条最长链更新答案 ans max(ans, dp[u] dp[v] 1); // 更新u往下走的最长链 dp[u] max(dp[u], dp[v] 1); } }这里核心在于每个节点维护两条最长链一条来自子树某个分支另一条来自另一个分支两条链在u节点汇合就形成了一条候选直径。这个方案最大的好处是遇到带权边也能用只需要把1改成加边权w缺点是递归深度大链状数据可能爆栈。我在P7807里用的还是两遍BFS因为按普及的定位边权基本都是1BFS写起来更快而且对后面的答案输出更直观。不过两套方案你都该熟因为你永远猜不到出题人会在哪一个变种题里给你埋带权边的坑。3. 离散化数据范围大得离谱时怎么活下来3.1 什么时候需要离散化“离散化”这个词对没接触过的同学第一反应是数学课本里的定义域离散化其实在竞赛题里就是一个操作把稀疏地分布在一个巨大值域里的数值映射成连续的整数序号。这题的场景里出现离散化的原因一般有两种。第一种是编号不连续。比如节点编号可能是“1号、10号、100号、1000号”这种虽然编号范围很大但实际只有N个节点。按编号上限去开数组不是不行但如果编号范围到1e9而实际节点只有2e5个那按编号上限开数组就是灾难必须压缩。第二种是附带属性值巨大。比如每个节点有一个“魔力阈值”或者“滋生等级”数值范围1e9但最多也就N种不同的值。我们关心的往往只是相对大小和是否相等这时候也需要离散化。打个比方一栋楼里的门牌号不是连续的而是101、1001、20001但是实际上只有3户人家。你不可能从1号到20001号每个门牌都砌一堵墙隔成一间房那太浪费了。离散化的做法是把这三个门牌号重新编号为0、1、2然后只管这三间房同时保留一张映射表随时能从新编号找回老门牌号。3.2 经典三步式离散化写法标准流程三个步骤我叫它“排序、去重、二分查找”。假设我们有若干个需要离散化的数值全存在all数组里同时有一份原始值需要拿到对应的新编号vectorint all; // 收集所有需要离散化的值 vectorint original; // 原始值需要转成新编号 // 第一步排序 sort(all.begin(), all.end()); // 第二步去重 all.erase(unique(all.begin(), all.end()), all.end()); // 第三步对每个原始值二分查找它的新编号 for (int x : original) { int id lower_bound(all.begin(), all.end(), x) - all.begin() 1; // 这里id就是从1开始的编号 // 后续所有需要按值开数组的地方都用id做下标 }这里有三个细节特别容易被忽略。第一unique之前必须sort否则相邻去重不彻底。你如果把unique放在sort前面得到的还带重复值后面lower_bound就可能映射错。第二lower_bound返回的是迭代器减去begin()得到下标下标默认从0开始。很多人习惯编号从1开始所以加1。这个看你个人习惯但一定要前后一致否则后面数组访问要么下标越界要么空一段。第三如果后面还需要由新编号找回原值可以开一个val数组val[id] x。或者直接用all[id-1]访问取决于加没加那个1。3.3 离散化之后的坐标系还原我见过很多同学离散化完后面统计时又拿原值当数组下标结果不是越界就是答案全错。原因在于他把映射关系和原值搞混了。正确的做法是在进入需要数组索引的流程之前先想清楚这一步我到底用的是“原值”还是“新编号”。如果后续要按魔力等级统计每种等级的数量可以用一个cnt数组下标是离散化之后的编号遍历节点数组拿节点等级对应的id去cnt[id]。如果后面要比较两个等级大小直接用id比就行因为id的单调性和原值的单调性完全一致。逻辑上我习惯在草稿纸上先写清楚哪些变量存原值哪些变量存新编号。宁可多定义几个vector也不要混用。混用一次调试一小时起步这不是夸张而是我真实踩过的坑。4. 完整解题流程与核心代码4.1 整体流程串一遍我现在把P7807魔力滋生的完整解题流程走一遍。这个顺序是我反复调试之后确定的照着写不容易乱读入节点数N以及N-1条边。如果题目里的节点编号或者魔力值范围巨大先把所有出现的大数值放进all做离散化得到新编号。用新编号建图vector g[新点数1]读入每条边的两个端点双向存储。从任意节点出发比如编号1跑一次BFS找到距离它最远的点a。从a出发再跑一次BFSdist[b]就是树的直径长度也就是这题要的核心答案。如果题目要求输出直径上的某种累计量还需要记录父节点从b回溯到a把路径拉出来处理。4.2 建图与读入细节树题有一个非常经典的坑题目说是一棵树但读入的时候未必按顺序给你端点而且如果编号需要离散化必须先收集端点再排序去重再统一编号。顺序反了会导致编号对不上。我贴一个安全读入方式适用于节点编号巨大、需要离散化的情况int n; cin n; vectorpairint, int edges; vectorint all; for (int i 0; i n - 1; i) { int 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()); // 再统一建图 for (auto e : edges) { int nu lower_bound(all.begin(), all.end(), e.first) - all.begin() 1; int nv lower_bound(all.begin(), all.end(), e.second) - all.begin() 1; g[nu].push_back(nv); g[nv].push_back(nu); }这里有个前提出现过多少个不同编号图就用多少个点。如果题目明确说N个节点但编号乱序那all.size()最终也应该等于N心里要有数。如果题目里顺便给了魔力等级之类的属性就把它也一起塞进all等节点编号映射完之后再单独映射属性值。4.3 直径长度计算与答案输出下面是完整的求直径代码。第一次BFS找到a第二次BFS从a出发结束后dist[b]就是直径长度#include bits/stdc.h using namespace std; const int MAXN 200005; vectorint g[MAXN]; int dist[MAXN]; int bfs(int s) { queueint q; memset(dist, -1, sizeof(dist)); q.push(s); dist[s] 0; int far s; while (!q.empty()) { int u q.front(); q.pop(); if (dist[u] dist[far]) { far u; } for (int v : g[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } return far; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // 如果节点编号需要离散化按上面4.2的写法替换这里的读入 for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } int a bfs(1); int b bfs(a); cout dist[b] \n; return 0; }留意两点。第一memset每次BFS都会重置dist所以第一次BFS找a第二次BFS从a开始dist[b]就是第二次遍历中离a最远的距离。第二如果整棵树只有1个节点那么第一次BFS返回1第二次BFS也返回1dist[1] 0输出0。这意味着单节点情况下最远距离为0这在大多数题目里是合理的。4.4 完整可提交代码与离散化变体上面代码假设节点编号已经紧凑且范围正常。如果P7807的输入编号很大不能直接开vector那就要把主函数里的读入部分替换成4.2节的写法。完整的流畅如下#include bits/stdc.h using namespace std; const int MAXN 200005; vectorint g[MAXN]; int dist[MAXN]; int bfs(int s) { queueint q; memset(dist, -1, sizeof(dist)); q.push(s); dist[s] 0; int far s; while (!q.empty()) { int u q.front(); q.pop(); if (dist[u] dist[far]) { far u; } for (int v : g[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } return far; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairint, int edges; vectorint all; for (int i 1; i n; i) { int 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 pointCount all.size(); for (int i 0; i pointCount 1; i) { g[i].clear(); } for (auto e : edges) { int nu lower_bound(all.begin(), all.end(), e.first) - all.begin() 1; int nv lower_bound(all.begin(), all.end(), e.second) - all.begin() 1; g[nu].push_back(nv); g[nv].push_back(nu); } int a bfs(1); int b bfs(a); cout dist[b] \n; return 0; }这个版本天然支持乱序、稀疏编号的树。如果你遇到的是普通1到N编号可以把我4.3节的简洁版本和这个离散化版本二选一看题目要求。5. 提交之后的血泪教训超时、内存与细节坑5.1 常见问题速查表我把自己和身边朋友踩过的坑汇总了一下整理成一张表很适合在WA之后快速对照表现可能原因解决办法答案比预期大很多BFS遍历时不区分父节点把树当成有环图反复走在BFS访问标记里用dist[v] -1判断天然规避回头路答案总是0第二次BFS的dist被重置后输出的是第一次的旧值一定要在第二次BFS结束后再访问dist[b]MLE邻接表开成了N*N或者开了多余的大数组用vector动态分配链式前向星也行TLE每个BFS都对整个数组memset数据量又很大用队列加vis时间戳或者只重置实际访问到的节点WA但逻辑看着没问题离散化后的id和原值混用所有按值开数组的位置都改成按idDFS递归爆栈用了递归DFS遍历链状树改用BFS或加递归栈大小设置这张表真的是我的“避坑备忘录”。每次遇到WA我都会先把表过一遍查得比IDE里瞎print快得多。5.2 手造样例与对拍经验我强烈建议用两个极端数据测自己的代码。第一个是“一条链”。比如N5边是1-2、2-3、3-4、4-5。这棵树直径一定是4也就是1号到5号的距离。如果输出不是4那多半是对直径定义理解错了或者图建成了单向边。第二个是“星形”。比如1号节点连着2、3、4、5其他节点不再互连。树上任意两个非中心叶子之间的距离都是2所以直径是2。这个数据可以快速验证第二次BFS找最远点是否准确。如果还想更严谨写一个对拍脚本。用随机数据生成器生成随机树一边跑你的正解一边跑一个朴素暴力。朴素做法就是N很小的时候对每个点都做一次BFS记录全局最大距离。N10以内的时候暴力一定正确几十组随机样例跑下来都一致那你的代码基本就稳了。我实际做题时会额外打印dist数组肉眼看一下距离分布是否合理。打印调试是最古老但最有效的手段尤其是判断“两次BFS状态没有清干净”这种恶性问题。5.3 离散化相关的三个隐蔽坑位离散化虽然就三行代码但坑位一点不少我单独拿出来说。第一个坑是“重复边”。如果输入里出现了重边而你没有提前去重all里的同一个值会出现多次。sort之后unique会去掉但edges里的重复边会导致图上出现两条同向边BFS时dist[v]已经访问过就不会重复更新所以重边本身不影响直径长度。但如果你要处理的是最短路径类问题重边会影响答案这时候就要提前对边去重。第二个坑是“0点还是1点起步”。离散化出来的id通常从1开始方便和vector的1-based遍历对齐。但有些人习惯从0开始于是g数组下标从0到pointCount-1。这个不致命但main函数里第一次bfs(1)可能面临“1号点根本不存在”的问题。你如果从1开始编号就一定要保证所有节点的id从1起步。我写的版本是从1起步所以bfs(1)是安全的。第三个坑是“属性值和编号混在一起离散化”。如果节点编号和魔力等级是两个不同的维度最好分开两个vector处理比如idxMap负责编号levelMap负责属性值。不要图省事把它们塞进同一个all那样后面id会互相污染。我印象里吃过一次这种亏最后排查到是在映射属性的时候误用了节点的id。从那以后我每遇到多维度离散化就分开处理。5.4 这道题为什么容易“样例过、提交挂”“样例过、提交挂”是这类普及题最典型的状态。原因往往不是算法问题而是输入输出的边界处理。比如N的范围没有认真读数组按2e5开但实际N是2e5加一比如多个测试点共用一个全局数组上次的残留数据污染了这次的结果比如忘了关同步流导致大输入下超时。这种题还有一种特别容易挂的情况你以为它是树但输入里某两个点之间可能有额外边或者存在自环。正规题目不会这样但为了防止被毒瘤数据背刺BFS写法的访问标记可以帮你挡住这种异常。只要dist[v] -1这个条件成立重边和自环都不会造成死循环。我个人交题前的固定检查清单是数组大小是不是MAXN配合题目上限全局变量有没有在每组数据之间清干净双向边是不是真的存了两条输出到底要换行还是直接输出整数是否打开了ios::sync_with_stdio(false)和cin.tie(nullptr)这些看起来都是小事但它们决定了你是1A还是连着WA五发。最后再分享一点我个人的体会。P7807这种“普及”题很多人一看带故事包装就先慌了其实模型复杂度不高纯粹是考你能不能从文字里抽出树和大值域这两套体系。我做这类题的经验是拿到题先别急着开IDE在草稿纸上把“输入什么——要建什么结构——用什么算法——输出什么”这四行写清楚20分钟后你会感谢这个习惯。树的直径BFS求法、离散化三步压缩法这两个工具越熟练下次遇到任何变形题哪怕它包装成“城市网络”“病毒传播”“魔力滋生”你都能快速脱掉马甲看到原型。祝大家刷题顺利。
