企业官网建设流程全解析

去年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; vector<int> 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 代码。我用 C++17 的写法给出一份可以直接提交的版本：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<int> 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^5，2×(n-1) 撑死也就是 2×10^5，int 不是完全够用吗？确实，单看这道题，int 够用。但我在教学时一直强调一个原则：涉及“乘法后减法”的运算，直接开 long long 是一个零成本的防御习惯。题目数据范围一旦放宽到 10^6 甚至更大，int 就溢出了。考场上改类型是很麻烦的，不如一开始就写对。

第三个细节是dfs(1, 0, 0)这个调用。根节点是 1，它的父节点不存在，所以用一个不存在的节点 0 来占位。这样在遍历根节点邻居时，不会有任何节点等于 0，也就不会误跳过任何真实邻居。这个“虚拟父节点”的技巧，在树题里几乎通用，建议直接记下来。

3.3 答案计算为什么是 2×(n-1)-maxDepth：手算验证一遍

这个公式是整道题的核心，我用一棵小树来手算验证一下，确保大家理解“为什么”。

假设输入是 8 个节点，边是：

• 1-2，1-3
• 2-4，2-5
• 3-6，3-7
• 7-8

这棵树的根是 1。从根出发，找出最长的一条链：1 → 3 → 7 → 8，一共 3 条边，所以 maxDepth = 3。

n = 8，n-1 = 7，2×(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 忘了特判 n=1 的情况

很多学生在写这道题时会忽略 n=1 的情况。当树只有 1 个节点时，没有边，从节点 1 出发，已经遍历了所有节点，一步都不用走，答案应该是 0。

如果不特判会怎样？n-1 = 0，dfs(1, 0, 0) 进去以后没有任何邻居，maxDepth 保持 0，ans = 0，其实代码也能输出正确结果。所以这道题里 n=1 不会出问题。但我要提醒的是，这只是一个巧合。在别的树题里，n=1 往往意味着特殊逻辑，比如没有边、没有父节点、没有答案源。如果每次都不考虑边界情况，迟早会栽跟头。形成了“先想边界”的习惯，考场上才能稳。

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 走到 2，2 的邻居里有 1，于是递归回到 1；1 的邻居里有 2，又递归到 2……无限循环，最终爆栈或者超时。

这个坑在我的教学里出现频率极高。原因很简单，很多同学在画树的时候，习惯性地认为“从上往下走”，默认不会回到父节点。但在代码里，树是无向图，邻居列表并不会区分上下关系。所以一定要显式地传入父节点，并在循环里跳过它。还有一个判断技巧：如果题目给的树有明确的父子关系，也可以在建树时只存子节点，这样就不需要父节点参数了。但那种情况需要题目明确保证输入顺序，GESP 这道题没有这个保证，所以还是传父节点最稳妥。

4.4 递归深度问题与迭代写法

树题用递归写 DFS 很自然，但当 n 达到 10^5 甚至更大时，如果树退化成一条链，递归深度也会达到 10^5 级别。大部分比赛环境的默认栈空间都能扛住这个深度，但有些老旧的评测环境或者 Windows 本地测试环境会出现栈溢出。

如果你担心递归爆栈，可以用栈模拟 DFS。代码逻辑不变，只是把系统递归栈换成显式栈：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<int> 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); } // 用栈模拟 DFS，tuple 存三个值：当前节点、父节点、当前深度 stack<tuple<int, 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; }

这段代码和递归版的效果完全一致，但它不会因为递归深度过大而爆栈。C++17 的结构化绑定auto [u, fa, dep] = st.top();在部分 GESP 评测环境中可能不受支持，如果环境是 C++14，可以改用get<0>(st.top())的方式访问 tuple 元素。总之，两种写法都掌握是最稳的。

下面是我根据教学中的经验，整理出来的常见错误速查表，考前翻一眼很管用：

这张表里的前四个问题，是每个学期我给学生讲这道题时几乎都会遇到的。把这些坑提前排掉，考场上至少能省下半个小时的调试时间。

5. 从“树上游走”延伸出去的几个变体考法

5.1 如果必须回根：答案就固定了

“必须回到根节点”的版本，本质上就是遍历完所有节点后原路返回。每条边要走两遍，所以答案是 2×(n-1)，没有任何优化空间。这类变体考的是“你能不能识别出题目的约束变化”。会做原题的同学，遇到这个版本应该 10 秒内改完代码。

还有一种中间形态：题目不问步数，而是问“游走结束后停在哪个节点”。那答案往往是“距离根节点最远的一个节点”，如果有多个，再根据题目要求的输出规则选择。理解了原题的贪心本质后，这类变体就是套公式而已。

5.2 需要输出游走序列：DFS 顺序有讲究

如果题目要求你输出一种合法的游走顺序，那就不是简单输出 DFS 序列了。因为你要保证所有节点都被访问，而且可能允许回溯。通常的做法是用 DFS 遍历整棵树，在进入节点时输出一次，子树遍历完毕回溯到当前节点时再输出一次当前节点，这样能够完整表达“走向子节点再回到父节点再走向下一个子节点”的路径。

这段伪代码逻辑大致是：先输出当前节点，然后遍历所有子节点，每次递归返回后再输出一次当前节点。这样输出的序列长度刚好就是路径上的节点序列，根据它就能推出步数。这类变体的考点在“DFS 回溯时的输出位置”，和原题统计最大深度的思路不太一样，但底层的遍历框架完全复用。

5.3 进阶：最长链问题通向树的直径

“从根出发找到最深路径”是单源最长链问题，它的进阶版是“整棵树中任意两点之间的最长距离”，也就是树的直径。树的直径有一个经典性质：从任意节点出发，找到最远节点 a；再从 a 出发，找到最远节点 b，a 到 b 的路径就是树的直径。这个结论在很多树上最优化问题里都很常用。

我建议备考 GESP 七级、八级的同学，在做完“树上游走”之后，顺手把树的直径题也刷一刷。因为这两个问题的核心遍历方式完全一样，都是 DFS 两次或一次记录最大深度。区别只是原题固定了起点是根，树的直径需要动态确定起点。把一道题吃透到能自然迁移到相邻问题，比闷头刷十道类似的题效率高得多。

6. 关于这道题，我最想分享的几个实操心得

最后说点题外话，也是我每次讲完这道题都会跟学生强调的几点。

第一，做树题一定要先画图。GESP 考场上发的是草稿纸，别让它空着。拿到“树上游走”，先把样例里的树按照输入一条边一条边画出来，然后从根开始，用手指沿着边“走”一遍，体会一下哪些边走了一次、哪些边走了两次。图一画出来，答案公式基本就能自己推出来了。我见过太多学生对着题目发呆十分钟，就是因为不肯动笔。

第二，代码不要一上来就追求“最优美的写法”。先把 DFS 框架搭好，跑通样例，再想优化。这道题的数据范围决定了，递归版和栈模拟版都能 AC，没必要在考场上搞什么花哨的迭代器或者全局函数指针。简单、清晰、能一次写对，比什么都重要。

第三，考后复盘比考试本身更重要。每道真题做完以后，试着改一改约束条件：如果不允许回到根呢？如果树是带权树呢？如果游走顺序必须满足某种规则呢？每一次改题，其实都是在锻炼你从“套模板”到“理解本质”的能力。GESP 六级的通过率并不算高，能拉开差距的，往往就是这种对基础题目的理解深度，而不是你背了多少个高级算法。