去年12月的GESP C六级真题里有一道“树上游走”不少学生考完出来跟我说“题面读懂了树也画出来了就是不知道下一步该怎么走。”这题在考场上看起来很温和——就是一棵树、一个起点、一个步数统计但它真正想考的是你对树的存储、DFS遍历逻辑以及一点贪心思维的综合运用。我把它单独拿出来写一篇是因为它非常适合准备GESP六级、正在从线性数据结构往树上算法过渡的同学。文章里我会从最基础的树怎么存开始讲到最后一行代码写完整个AC过程把每个“为什么”都交代清楚顺带把考场上的高频坑一并排掉。1. 拿到题先别急着敲代码——先想清楚“游走”到底在问什么1.1 题目模型还原一棵树和一个步数统计先说结论这道题考的是“在树上从根出发遍历全部节点求最小移动步数”。题目给出的是一棵有 n 个节点、n-1 条边的无向连通图也就是标准的树通常从节点 1 出发。每沿着一条边移动一次就算一步。问题是最少要走多少步才能把所有节点都“访问”到。注意这里“访问”不是说要走到每个节点正好一次。树的结构决定了除了根节点之外每个节点只有一条路可以初次到达。如果要求每个节点只经过一次那本质上就是在找一条“一笔画”路径但树要做一笔画根本走不全——你走到叶子就回不来了。所以这道题的“游走”更准确的描述是允许重复经过节点和边但目标是让所有节点至少被经过一次统计最少的步数。很多同学做题时把问题复杂化以为要模拟搜索、记忆化之类的。其实这道题完全不需要复杂的搜索它考的是你能不能把一个具体场景抽象成“树上的最优遍历规则”然后转换成代码。这个抽象过程恰恰是GESP六级“算法思维”类题目的出题套路不考偏题怪题但要求你对基础概念有真正的理解而不是背模板。1.2 为什么“不必回根”是解题的核心突破口这题最关键的一条规则题面里通常没有直接说明但根据样例输出能反推出来游走结束后不要求回到出发点。也就是说你可以从根出发一路走把所有节点逛完最后停在一个节点上。这一点决定了整个答案的计算方式。我们来推一下。树有 n 个节点就有 n-1 条边。如果要求“从根出发遍历所有节点最后必须回到根”那很简单每条边都得走两遍下去一遍、回来一遍总步数固定是 2×(n-1)。但这里不要求回根那就意味着最后你停下来的那一段路是不需要“走回来”的。说得更直白一点你在树上逛景点每个景点之间的连廊必须走一遍才能看到所有地方。唯一能省掉的是你最后从根走到最终停留点的那条路径——因为这条路你只需要走一次不用再原路返回。为了让总步数最少你要让“只走一次”的这段路尽可能长。换句话说答案等于“每条边来回两遍的总步数”减去“从根到某个叶子节点的最大深度”。用我自己的话说这题本质上是在让你找树上“从根开始的最长链”。最长链上的边只走一遍其他边全部要走两遍。很多同学看到“游走”就开始模拟 DFS 路径、记录访问顺序却忽略了这个简单的贪心规则结果代码越写越复杂还容易错。2. 树的存储方案选型邻接表为什么是考场上的默认答案2.1 邻接矩阵和邻接表的时间空间对比确定了“要存树”这个前提后下一步就是选存储结构。GESP 六级的题n 的范围一般能到 10^5 这个量级。如果考试时用邻接矩阵开一个 int 的二维数组int a[100005][100005]光是算一下内存就知道不可能——100005 的平方大约是 10^10 个 int换算过来就是 40000MB什么机器都扛不住。而且就算内存允许遍历一个点的所有邻居时需要扫描整行时间复杂度也完全不对。所以树的存储必须用邻接表。邻接表的核心思路是只存储“实际存在的边”每个点存一个“邻居列表”。对于一棵 n 个节点的树一共只有 n-1 条边用邻接表存空间是 O(n) 级别。访问某个点 u 的所有邻居只需要遍历 u 的邻居链表总复杂度也是 O(n)。这才是树题的标准姿势。有的同学习惯用数组模拟链表的方式来实现邻接表也就是所谓的“链式前向星”它用 head 数组记录每个点的第一条边用 edge 数组存边的目标节点和 next 指针。这种写法在竞赛圈很常见优点是常数小、省内存。但对 GESP 六级这个阶段来说C 的 vector 是实现邻接表最舒服、最不容易写错的方式没有之一。2.2 vector 邻接表的代码模板和双向边陷阱用 vector 实现邻接表的核心代码非常短#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint tree[MAXN]; int main() { int n; cin n; for (int i 1; i n; i) { int a, b; cin a b; tree[a].push_back(b); tree[b].push_back(a); } return 0; }这里最容易犯的一个错误是只 push 一条边。很多新手在学“有向图”时习惯了只存一条方向但树是无向图节点 a 和节点 b 之间的边两边都要记录。只存一边的话DFS 从根往子节点走没问题但如果你要从任意点出发遍历就会漏掉某些邻居导致整个游走过程不完整。注意树是特殊的无向图。所有“相邻”关系都是双向的存储时必须两侧同时入表。这是树题里写邻接表最大的一个细节也是最常见的 WA 原因。vector 邻接表最舒服的地方在于遍历的时候可以直接用范围 for 循环for (int v : tree[u])不需要维护任何额外的指针逻辑。在考场上代码越简单出 bug 的概率越低。我见过不少学生用链式前向星时next 数组和 edge 数组混在一起一调就是半小时其实在六级这个阶段完全没必要。3. 核心代码逐行拆解DFS 函数怎么写才不会懵3.1 DFS 参数设计当前点、父节点、当前深度树上的 DFS 是树的遍历里最常用的方法但参数设计很关键。常见的错误是只传一个当前节点 u然后在函数内部用一个 vis 数组来标记哪些点访问过了。在树上这样做其实有点“绕”因为树本身没有环你只需要避免“走回父节点”就行。换句话说只要在 DFS 时把当前节点的父节点作为参数传下去看到邻居里有这个父节点就直接跳过不需要额外的 vis 数组。DFS 函数建议这样设计int maxDepth 0; void dfs(int u, int fa, int depth) { maxDepth max(maxDepth, depth); for (int v : tree[u]) { if (v fa) continue; dfs(v, u, depth 1); } }这段代码的核心逻辑就三句话第一句每走到一个节点尝试更新最大深度第二句遍历当前节点的所有邻居第三句如果邻居是父节点就跳过否则继续往下递归。代码量非常少但包含的思维量并不小。depth这个参数记录的是“从根到当前节点经过了几条边”也就是当前节点在树中的深度。根节点的深度为 0它的子节点深度是 1依次往下。maxDepth 最终存的就是从根出发能走到的最远距离也就是最长链上边的条数。为什么不用 vis 数组因为树的结构本质上没有环唯一的“回头路”就是走回父节点。用 fa 参数判断既省空间又省时间。如果硬要加一个 vis 数组虽然不会错但多了一个全局数组要维护还容易忘记初始化在复杂度上也完全没有必要。3.2 完整 AC 代码从建树到输出答案一步不落把前面的存储和 DFS 组合起来加上最后的答案计算就是完整的 AC 代码。我用 C17 的写法给出一份可以直接提交的版本#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint tree[MAXN]; int maxDepth 0; void dfs(int u, int fa, int depth) { maxDepth max(maxDepth, depth); for (int v : tree[u]) { if (v fa) continue; dfs(v, u, depth 1); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { int a, b; cin a b; tree[a].push_back(b); tree[b].push_back(a); } dfs(1, 0, 0); long long ans 2LL * (n - 1) - maxDepth; cout ans \n; return 0; }这里有几个细节值得单独说说。第一个是ios::sync_with_stdio(false); cin.tie(0);这两行。GESP 的评测环境里如果 n 比较大不关同步的话cin 读入可能比 scanf 慢不少极端情况下会超时。虽然这道题的数据量未必会卡这么死但养成写这两行的习惯能让你在其他题里少吃亏。第二个细节是答案用long long来存。可能有同学会问n 最多 10^52×(n-1) 撑死也就是 2×10^5int 不是完全够用吗确实单看这道题int 够用。但我在教学时一直强调一个原则涉及“乘法后减法”的运算直接开 long long 是一个零成本的防御习惯。题目数据范围一旦放宽到 10^6 甚至更大int 就溢出了。考场上改类型是很麻烦的不如一开始就写对。第三个细节是dfs(1, 0, 0)这个调用。根节点是 1它的父节点不存在所以用一个不存在的节点 0 来占位。这样在遍历根节点邻居时不会有任何节点等于 0也就不会误跳过任何真实邻居。这个“虚拟父节点”的技巧在树题里几乎通用建议直接记下来。3.3 答案计算为什么是 2×(n-1)-maxDepth手算验证一遍这个公式是整道题的核心我用一棵小树来手算验证一下确保大家理解“为什么”。假设输入是 8 个节点边是1-21-32-42-53-63-77-8这棵树的根是 1。从根出发找出最长的一条链1 → 3 → 7 → 8一共 3 条边所以 maxDepth 3。n 8n-1 72×(n-1) 14。最大深度是 3所以答案是 14 - 3 11。你可以手动模拟一下1→2→1→3→6→3→7→8→7→3→1这是一条从 1 出发、访问所有节点、最终停在 1 的路径但它有 10 步而且没有走到 4、5不对我重新走1→2→4→2→5→2→1→3→6→3→7→8一共 11 步中途访问了 4、5、6、7、8最终停在 8。这正好就是最优答案。为什么最优路径一定会停在最长链的末端因为只有这条链上的边“只走一次”时省下的步数最多。其他任何一条链长度都小于 maxDepth省下的步数就少总步数就多。这条推理链清晰、简单考场上只要想通了代码几乎不会写错。提示如果题目改成“游走结束后必须回到根节点”那答案就直接是 2×(n-1)不需要求最深路径。这两种问法一字之差解法完全不同考试时一定要先看清楚。4. 考场和实战中的高频坑我在帮学生调错时遇到最多的四个问题4.1 忘了特判 n1 的情况很多学生在写这道题时会忽略 n1 的情况。当树只有 1 个节点时没有边从节点 1 出发已经遍历了所有节点一步都不用走答案应该是 0。如果不特判会怎样n-1 0dfs(1, 0, 0) 进去以后没有任何邻居maxDepth 保持 0ans 0其实代码也能输出正确结果。所以这道题里 n1 不会出问题。但我要提醒的是这只是一个巧合。在别的树题里n1 往往意味着特殊逻辑比如没有边、没有父节点、没有答案源。如果每次都不考虑边界情况迟早会栽跟头。形成了“先想边界”的习惯考场上才能稳。4.2 输入输出缓冲区导致的超时有些同学在本地测试小数据时一切正常一提交就超时尤其当 n 到 10^5 级别时cin 的默认同步模式会慢得离谱。标准输入流为了兼容 C 的 scanf/printf默认会和 stdio 同步这个同步过程有额外开销。数据量一大差距就非常明显。解决办法就一行代码ios::sync_with_stdio(false);最好再加上cin.tie(0);。这两句话的作用分别是“解除 cin 与 stdio 的同步”和“取消 cin 与 cout 的绑定”可以让 C 的输入输出速度快很多。如果还担心不够快可以用 scanf/printf甚至自己写快读函数。但在 GESP 六级这种级别的考试里关同步基本就足够了。4.3 父节点判断写错导致死递归用 vector 邻接表存树时每条无向边会被存储两次。如果 DFS 里不判断父节点会发生什么你自己想一下从 1 走到 22 的邻居里有 1于是递归回到 11 的邻居里有 2又递归到 2……无限循环最终爆栈或者超时。这个坑在我的教学里出现频率极高。原因很简单很多同学在画树的时候习惯性地认为“从上往下走”默认不会回到父节点。但在代码里树是无向图邻居列表并不会区分上下关系。所以一定要显式地传入父节点并在循环里跳过它。还有一个判断技巧如果题目给的树有明确的父子关系也可以在建树时只存子节点这样就不需要父节点参数了。但那种情况需要题目明确保证输入顺序GESP 这道题没有这个保证所以还是传父节点最稳妥。4.4 递归深度问题与迭代写法树题用递归写 DFS 很自然但当 n 达到 10^5 甚至更大时如果树退化成一条链递归深度也会达到 10^5 级别。大部分比赛环境的默认栈空间都能扛住这个深度但有些老旧的评测环境或者 Windows 本地测试环境会出现栈溢出。如果你担心递归爆栈可以用栈模拟 DFS。代码逻辑不变只是把系统递归栈换成显式栈#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint tree[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { int a, b; cin a b; tree[a].push_back(b); tree[b].push_back(a); } // 用栈模拟 DFStuple 存三个值当前节点、父节点、当前深度 stacktupleint, int, int st; st.push({1, 0, 0}); int maxDepth 0; while (!st.empty()) { auto [u, fa, dep] st.top(); st.pop(); maxDepth max(maxDepth, dep); for (int v : tree[u]) { if (v fa) continue; st.push({v, u, dep 1}); } } long long ans 2LL * (n - 1) - maxDepth; cout ans \n; return 0; }这段代码和递归版的效果完全一致但它不会因为递归深度过大而爆栈。C17 的结构化绑定auto [u, fa, dep] st.top();在部分 GESP 评测环境中可能不受支持如果环境是 C14可以改用get0(st.top())的方式访问 tuple 元素。总之两种写法都掌握是最稳的。下面是我根据教学中的经验整理出来的常见错误速查表考前翻一眼很管用错误类型典型现象根因解决办法邻接表只存单向边遍历漏节点答案偏小误解无向图存储两侧都 push_back忘记传父节点递归死循环爆栈或超时树被当成有向图处理dfs 加 fa 参数并判断不关输入输出同步大数据超时cin 默认同步开销大加 ios::sync_with_stdio(false)用 int 存答案数据放宽后溢出忽视取值范围变化用 long long 计算不明白“不要求回根”答案比样例大 2(n-1)误以为必须回根确认题面要求减去 maxDepth这张表里的前四个问题是每个学期我给学生讲这道题时几乎都会遇到的。把这些坑提前排掉考场上至少能省下半个小时的调试时间。5. 从“树上游走”延伸出去的几个变体考法5.1 如果必须回根答案就固定了“必须回到根节点”的版本本质上就是遍历完所有节点后原路返回。每条边要走两遍所以答案是 2×(n-1)没有任何优化空间。这类变体考的是“你能不能识别出题目的约束变化”。会做原题的同学遇到这个版本应该 10 秒内改完代码。还有一种中间形态题目不问步数而是问“游走结束后停在哪个节点”。那答案往往是“距离根节点最远的一个节点”如果有多个再根据题目要求的输出规则选择。理解了原题的贪心本质后这类变体就是套公式而已。5.2 需要输出游走序列DFS 顺序有讲究如果题目要求你输出一种合法的游走顺序那就不是简单输出 DFS 序列了。因为你要保证所有节点都被访问而且可能允许回溯。通常的做法是用 DFS 遍历整棵树在进入节点时输出一次子树遍历完毕回溯到当前节点时再输出一次当前节点这样能够完整表达“走向子节点再回到父节点再走向下一个子节点”的路径。这段伪代码逻辑大致是先输出当前节点然后遍历所有子节点每次递归返回后再输出一次当前节点。这样输出的序列长度刚好就是路径上的节点序列根据它就能推出步数。这类变体的考点在“DFS 回溯时的输出位置”和原题统计最大深度的思路不太一样但底层的遍历框架完全复用。5.3 进阶最长链问题通向树的直径“从根出发找到最深路径”是单源最长链问题它的进阶版是“整棵树中任意两点之间的最长距离”也就是树的直径。树的直径有一个经典性质从任意节点出发找到最远节点 a再从 a 出发找到最远节点 ba 到 b 的路径就是树的直径。这个结论在很多树上最优化问题里都很常用。我建议备考 GESP 七级、八级的同学在做完“树上游走”之后顺手把树的直径题也刷一刷。因为这两个问题的核心遍历方式完全一样都是 DFS 两次或一次记录最大深度。区别只是原题固定了起点是根树的直径需要动态确定起点。把一道题吃透到能自然迁移到相邻问题比闷头刷十道类似的题效率高得多。6. 关于这道题我最想分享的几个实操心得最后说点题外话也是我每次讲完这道题都会跟学生强调的几点。第一做树题一定要先画图。GESP 考场上发的是草稿纸别让它空着。拿到“树上游走”先把样例里的树按照输入一条边一条边画出来然后从根开始用手指沿着边“走”一遍体会一下哪些边走了一次、哪些边走了两次。图一画出来答案公式基本就能自己推出来了。我见过太多学生对着题目发呆十分钟就是因为不肯动笔。第二代码不要一上来就追求“最优美的写法”。先把 DFS 框架搭好跑通样例再想优化。这道题的数据范围决定了递归版和栈模拟版都能 AC没必要在考场上搞什么花哨的迭代器或者全局函数指针。简单、清晰、能一次写对比什么都重要。第三考后复盘比考试本身更重要。每道真题做完以后试着改一改约束条件如果不允许回到根呢如果树是带权树呢如果游走顺序必须满足某种规则呢每一次改题其实都是在锻炼你从“套模板”到“理解本质”的能力。GESP 六级的通过率并不算高能拉开差距的往往就是这种对基础题目的理解深度而不是你背了多少个高级算法。