GESP C六级2024年12月的第一道编程题“树上游走”说难不难说简单也不简单。它不像搜索题那样需要你写一个繁重的状态转移也不像图论难题那样必须掌握LCA或者树链剖分但它把“树”这个数据结构最基本的性质考了个透——深度的计算、DFS遍历的顺序以及一条路径重复次数的最优化。如果你在考场上把这道题当模拟题去一步步“走”大概率会栽在时间复杂度和思维陷阱上如果能想到“最少步数 所有边走两遍 - 最长的那条路”十分钟就能拿到满分。这篇文章我打算从题目拆解、算法推导、代码实现、考场防坑四个角度把这道题讲透顺带说说它对后续GESP六级备考的启示。1. 题目解读GESP六级为什么选“树上游走”当第一题1.1 从题面到考点这是一道伪装成模拟的数学题先还原一下这道题最常见的题面给定一棵n个节点的树节点从1到n编号初始时你在1号节点。你每次可以沿着一条边走到相邻节点目标是把所有节点都“游走”到即访问过最后停在任意一个节点都行问最少需要走多少步。很多同学一看到“游走”两个字第一反应就是“模拟走路”从1出发用一个DFS去搜所有可能的访问顺序然后取最小值。但请注意这里的访问顺序是任意的一棵树有n!种排列方式哪怕n只有15你都搜不完更别说GESP六级的数据范围一般会开到10的5次方级别。这道题的真正考点是把“最少游走步数”这个看似需要搜索的问题转化为一个数学结论。树这种结构有一个很重要的特点任意两点之间路径唯一且没有环。因为路径唯一所以一旦你为了访问某个子树跑了进去就必须原路返回到分岔口才能再去访问另一棵子树。这个“一去一回”的性质直接决定了步数的计算方式。1.2 结合GESP大纲六级到底在考什么能力我在备赛的时候专门研究过GESP各等级的考察范围。一级到四级基本围绕顺序结构、循环、数组、函数、简单排序这些地基到了五级开始引入递归、DFS、回溯而六级的核心考点就落到了“树”和“图”上尤其是树的遍历、树的深度、最短路初步以及简单的贪心思维。“树上游走”正好卡在这个位置。它不要求你会树链剖分、倍增LCA这种高级数据结构但要求你必须掌握两点第一会用邻接表存一棵无根树第二能通过一次DFS求出从根到每个节点的深度。这两件事放在六级这个阶段非常合理既不是一级那种“照着写循环”的送分题也不是七级八级那种需要综合算法的压轴题。GESP把这个题放在第一道编程大题说明出题人想用一道“思维转弯题”来区分“会背模板”和“真正理解树”的考生。1.3 数据范围与限制出题人留下的暗示一般来说这种题n的上限在10^5量级边的数量是n-1。这意味着什么呢第一O(n^2)的算法必挂哪怕你写的是看起来很美的DP或递归搜索第二O(n)或O(n log n)的算法能过一次DFS完全够用第三因为只有一棵树、单组数据所以不用考虑多组测试的清空问题但递归的层数有可能达到10^5这个细节在后面的代码部分我会专门说。另外从“不需要回到起点”这个条件你应该能嗅到一丝不寻常。如果题目要求“游走完回到1号节点”那答案就是固定的2*(n-1)非常无聊正是因为终点可以任意选题目才真正有了思考空间。这道题能成为六级第一题不是因为代码量大而是因为那个“少走一条最长路”的结论不容易一眼看出来。2. 核心算法思路别真去“走”要算“少走哪条路”2.1 朴素模拟为什么不可行先说说为什么不能走“模拟”这条路。假设你用一个DFS枚举访问顺序树的节点数一多状态空间立刻爆炸。哪怕做一个贪心版本每次选择离当前节点最近的未访问节点在树上也没有简单规则能保证全局最优。你会陷入“先访问左子树还是右子树”“走到一半要不要折返”的泥潭最后写出一堆难以调试的搜索代码。实际上这道题的本质是“树上最小遍历问题”它和经典的“邮递员问题”在树上的简化版非常像。既然所有边都要被覆盖到那就先把“必须走的步数”算出来再看“哪些边可以少走”。2.2 关键观察每条边最少走几次哪条边能只走一次把树看成一堆边连接起来的节点集合。任意一条边e如果把这条边删掉整棵树会被分成左右两部分。你从1号节点出发最终总要把这两部分都访问完。如果你最终停在右边部分那么对于边e来说你从左边跨到右边之后就不需要再跨回去了——也就是说这条边上你只走了一次而所有你走过之后还需要原路返回的边都必须走两次。我举个小例子你立刻明白。假设树是这样1-22-32-4。从1出发访问所有节点后停在4。走法可以设计成1→2→3→2→4。这里边1-2走了一次从1到2边2-3走了两次去3再回2边2-4走了一次最后到4。总步数4而2*(n-1)2*36少走的那2步正好就是从1到终点4的路径长度2。所以我们可以得到一个通用公式总步数 2*(n-1) - (从1号节点到终点的那条路径长度)。为了让总步数最小我们需要让括号里减掉的那个数最大也就是让终点尽量远离1号节点。这个“从1出发能走到的最远距离”其实就是以1为根时整棵树的最大深度。一次DFS就能求出来复杂度O(n)。2.3 一个最容易被带偏的“陷阱”树的直径到底能不能用很多刷过题的同学看到“找树上最远点”的第一反应是“树的直径”然后直接套“两次DFS求直径”的模板算出整棵树直径长度d再用2*(n-1)-d作为答案。我必须提醒你这个做法只有在“起点也可以任意选择”时才正确而GESP这道题明确是从1号节点出发你不能自由选择起点。我构造一个反例给你看。假设n8树的边为1-22-33-43-52-66-77-8。以1为根时从1到最深节点8的距离是1→2→6→7→8长度4但整棵树的直径是4→3→2→6→7→8长度5端点分别是4和8。如果错误套用直径答案是27-59正确做法是27-410。差一步。这个区别在考场上就是10分和0分的差别。那为什么会有这种差异因为树的最小遍历路径本质上是你“只走一次”的那些边必须连成一条从起点到终点的连续路径。如果你从固定起点1出发这条路径必须从1开始那它能延伸的最长长度就是从1出发的最深路径而树的直径只是“全树任意两点间的最长距离”不一定经过1号节点。理解了这个区别你就永远不会在这种题上犯糊涂了。2.4 时间复杂度与空间复杂度分析一次DFS遍历整棵树每个节点和每条边各访问一次时间复杂度O(n)。空间上邻接表存储所有边需要O(n)个vector节点、O(n)条边的存储depth数组和递归栈都是O(n)整体空间O(n)。对于10^5的数据量这个复杂度非常宽裕就算n开到10^6只要改掉递归爆栈问题也完全能跑。如果题目稍微变形要求“游走完必须回到1号节点”那答案就是固定的2*(n-1)连DFS都不用求深度了如果题目变形为“起点和终点都可以任选”那就是标准的“减去树的直径”需要先求直径。备考时建议把这三种变体都练一遍这样不管考场上考哪种你都能快速反应过来应该套哪个结论。3. 参考代码与细节实现邻接表、DFS、防爆栈3.1 完整参考代码C17递归版下面这份代码是考场上的主力版本短小精悍适合绝大多数数据范围#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint g[MAXN]; int depth[MAXN]; void dfs(int u, int fa) { for (int v : g[u]) { if (v fa) continue; depth[v] depth[u] 1; dfs(v, u); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n - 1; i) { int a, b; cin a b; g[a].push_back(b); g[b].push_back(a); } dfs(1, 0); int mx 0; for (int i 1; i n; i) { mx max(mx, depth[i]); } int ans 2 * (n - 1) - mx; cout ans \n; return 0; }3.2 关键代码逐段讲解为什么这样写才稳先看存图。我用的是vectorint g[MAXN]也就是邻接表。因为树是无向图输入一条边a b时必须在a的邻居里加入b同时在b的邻居里加入a否则DFS会漏掉一半方向。这一点看起来基础但我在平时辅导时见过太多同学只push了一边结果样例过了、大数据全WA。DFS的写法是dfs(u, fa)u是当前节点fa是它的父节点作用是防止走回头路。因为无向图的邻接表里u的邻居包含它的父节点如果不判断v faDFS就会在父子之间来回跳轻则死循环重则递归栈溢出。树DFS判断父亲这个写法是六级必须形成肌肉记忆的模板。depth数组记录从根1到每个节点的深度根节点深度为0。注意如果题目把“步数”定义为“经过的节点数”而不是“经过的边数”那depth[1]要初始化为1。我按边数来写因为游走一步对应一条边这样和题目示例最贴合。3.3 两种图的存储方式对比邻接表还是链式前向星说到存图我顺便把几种常见方式放在一起对比一下存储方式适用n内存占用编码复杂度遍历速度邻接矩阵n≤1000O(n^2)n10^5直接爆最低慢vector邻接表n≤10^6O(n)较优低中链式前向星n≤10^6或更大O(n)最优中快GESP六级的数据范围通常用vector邻接表就够代码简单不容易写错。如果你追求极致性能或者题目n到了10^6级别再考虑链式前向星。对大多数考生来说vector邻接表已经是一个足够可靠的选择——别在存储方式上过度设计考场上多省一分钟是一分钟。3.4 非递归求深度防递归爆栈的稳妥方案递归在Linux评测系统下一般能跑10^5深度但Windows本地Dev-C默认栈比较小遇到一条链状的树比如1-2-3-...-n递归深度会直接到n有可能爆栈。如果你不想赌评测环境的栈大小可以用一个显式栈模拟DFSint fa[MAXN], depth[MAXN]; void calcDepth() { stackint st; st.push(1); fa[1] 0; depth[1] 0; while (!st.empty()) { int u st.top(); st.pop(); for (int v : g[u]) { if (v fa[u]) continue; fa[v] u; depth[v] depth[u] 1; st.push(v); } } }这段代码的逻辑和递归版完全一致从根节点开始每遇到一个邻居v只要v不是父节点就记录它的父亲并更新深度然后把v压入栈中。因为栈是显式的不受系统递归栈大小限制所以即使n10^6也不会爆。缺点是需要额外维护一个fa数组代码稍微长一点。我的建议是平时练习两种写法都写一遍考场上如果时间充裕就用递归版如果题目n特别大或者你本地测试发现爆栈立刻切换到非递归版。3.5 输入输出优化的实测心得GESP不少考生用cin n直接读在n10^5时其实能过但加上这两行更保险ios::sync_with_stdio(false); cin.tie(nullptr);这两行能让cin的读取速度快很多而且不会影响代码逻辑。如果n到了10^6级别我更推荐直接用scanf或自写快读。有一个实测数据n10^5、边数10^5的稠密树不开同步的cin大概耗时几十毫秒开了同步后几乎可以忽略但如果数据量再涨十倍差距就会拉大到可能出现超时。总的原则是能加优化就加上不加也不影响正确性但加了更稳。4. 考场上容易踩的坑从实测错误看问题本质4.1 最常见的翻车点把题目当模拟游走去写搜索我见过不少同学的考场代码真的去枚举访问顺序或者用一个二维数组记录哪些节点已经访问然后一步步“走”。这种写法的致命问题在于状态爆炸。哪怕你用了DFS贪心剪枝n稍微一大就超时更麻烦的是这种代码往往又长又乱调bug调到崩溃。实际上你只需要把问题抽象成“2*(n-1)-最大深度”这个数学公式代码长度直接缩短到三四十行。所以拿到这类题先别急着敲键盘花两分钟在草稿纸上画棵树、总结规律远比闷头写代码重要。4.2 双向边没处理干净DFS死循环的经典元凶如果你写完DFS后程序一直在跑、不出结果九成是没判断父节点。我再强调一遍无向图存的边是双向的DFS时必须用if (v fa) continue;排除回头路。还有一种隐蔽情况如果你用全局数组保存father但多组测试数据时没有把father重置也可能出现旧数据干扰。我习惯在DFS函数参数里直接传父节点而不是用全局数组这样从代码结构上就杜绝了“忘记重置”的问题。4.3 边界情况n1和n2最容易漏当n1时树只有1号节点没有边。按公式2*(n-1)-mx 20-0 0答案应该是0步因为起点就在唯一节点上不需要动。当n2时只有一条边1-2最大深度为1答案21-11从1走到2正好结束。这两个边界在写代码时要确保能跑对。很多同学在草稿纸上手推n5、n6的用例反而把最简单的n1漏了结果在评测系统里白丢一个测试点。4.4 答案用int还是long longn10^5时2*(n-1)大约是210^5int完全装得下。但如果题目数据范围放宽到10^6210^6也还是int范围只有当n到10^9这种离谱量级时基本不会出现在GESP六级才必须开long long。我的建议是养成用long long计算答案的习惯反正也不费事多一份保险。4.5 常见问题速查表我把考场上最常遇到的几个问题整理成一张表方便你快速对照症状可能原因解决办法程序运行超时用搜索枚举访问顺序递归栈过深改用公式法换非递归DFS死循环或栈溢出没判断父节点DFS不断回头加if (v fa) continue;答案偏大忘记减去最大深度终点认为必须回起点检查公式2*(n-1)-mx答案偏小错误使用整棵树的直径而非从1出发的深度明确起点固定为1别套直径结论本地正确、提交WA数组开小了读入没优化多组数据没清空检查MAXN加快读初始化全局数组4.6 一个隐蔽的细节最大深度到底怎么算我第一次做这道题时把depth[1]初始化成了1结果答案比标准小1。后来仔细读题发现“游走一步”指的是走一条边所以根节点的深度应该从0开始。如果你把“深度”理解成“经过的节点数”那么从1到3号节点经过3个节点但实际走的边数是2。建议在看完样例后先用样例手算出步数再去对公式这样能尽早发现定义上的偏差。5. 从这道题看GESP六级备考工具包与思维升级5.1 这道题背后的“算法工具包”“树上游走”虽然只是一道题但它背后的工具包在六级考试里反复出现第一用邻接表存无向树第二DFS带父节点遍历第三求树的深度、子树大小、父亲节点第四理解“路径长度”和“节点数”的区别。这些知识点几乎就是GESP六级树形题目的基石。如果你能把这道题吃透后面遇到“树上最短路问题”“树的直径问题”“树形DP入门题”上手速度会快很多。5.2 从GESP一级到六级学习路径上的递进关系我整理过一条很清晰的学习路线一级和二级搞懂顺序、分支、循环三级开始接触数组和冒泡排序这类经典算法四级学函数、递归、简单回溯五级练DFS、BFS、枚举优化六级就是树和图的主场。“树上游走”正好是六级前期的一道典型题——它不要求你掌握多深的算法但要求你能把“树”这种结构转成代码并用数学思维简化问题。如果你现在还在五级打转建议先把递归和DFS练扎实再来看树如果你已经过了六级想冲七级八级那这道题里的“防爆栈”“邻接表”等细节也是后续学习LCA、树链剖分的基本功。5.3 备考建议从真题出发的三步走我建议你在考前按这个顺序练习第一步用二十分钟手写一个树的DFS功能是打印每个节点的深度和父节点。这个练习能帮你熟悉邻接表和递归两个关键点还能暴露出你对无向图处理是否熟练。第二步专门找三五道“树上最小步数”“树上最长路径”的题目练手每做完一道都在草稿纸上画出树的形态验证公式是否和手推步数一致。第三步考前一晚别再刷难题把邻接表建图、DFS防回头、求深度和直径这几个模板默写一遍。考试时心态稳了这些“肌肉记忆”才能正常发挥。5.4 一个自力更生的调试技巧最后分享一个我常用的调试方法写一个随机树生成器输出n和n-1条边同时用暴力搜索在小数据下算正确结果再和你的公式法结果对比。比如随机生成n8的树暴力枚举所有访问顺序n小的时候可行对比两种结果是否一致。这个技巧不仅能帮你验证公式还能帮你发现代码里的细节错误。如果你懒得写暴力版也可以手推几组n4、5、6的树形用例把每一步走法写在纸上数出步数再对答案。我个人在实际操作中的体会是这种“树上走最少步”的题最怕的不是你不会DFS而是你被“游走”两个字带偏把它当成搜索模拟题。每次遇到这类题我都先画一棵六七个节点的树把自己当成题目里的那个人从起点一步步走到终点数出真实步数再和2*(n-1)-mx这个公式对照。多走几次你对“为什么少走一条最长路”的理解就会从“背结论”变成“真懂”考场上的反应速度自然就快了。希望这篇拆解能帮你在下一次碰到树形题目时少走两步弯路。