PAT甲级里做过的图论题不少但是A1021 Deepest Root是少数几道我做完之后又专门回头复盘了一整晚的题。表面上看它只是让你在一棵树上找几个深度最大的点真写起来才发现判断连通性、找树的直径端点、处理单节点的边界几乎每一步都藏着扣分点。这篇文章不只是贴一份能AC的代码我想把题面背后的图论模型、两次DFS为什么成立、以及我实际提交过程中踩到的坑一起讲清楚。如果你是正在准备PAT甲级的考生或者正在练树与图的算法题这篇文章应该能帮你省下不少来回查资料和反复提交的时间。1. 题面读三遍之后我发现它真正考的是三件事1.1 N个结点、N-1条边这个描述藏了什么先还原题目的原始样貌给定N个结点和N-1条边每个结点编号从1到N边是无向的。题目要求先判断这个图是不是一棵树如果它不是树输出它有多少个连通分量如果它是树就找出所有“最深根”——即以该结点为根时整棵树的高度能达到最大值。很多人的第一反应是这不就是做一遍DFS求高度吗但仔细想题目给了N个点、N-1条边这个数量关系本身就是一个强烈的信号。对于无向简单图N个点、N-1条边、并且连通等价于它是一棵树。为什么因为在一个连通图里任意生成树恰好有N-1条边如果这个图有N-1条边且仍然连通它就不能再删掉任何一条边而不破坏连通性于是不能有环只能是树本身。换句话说判断“是不是树”其实只需要回答一个问题这个图连通吗连通就是树不连通就输出连通分量个数。这个转化是所有后续步骤的地基可惜很多人一上来就去计算深度完全没有意识到第一步应该是连通性判断。一旦图不连通DFS返回的深度数据就是局部信息没有任何全局意义代码写得再漂亮也会在逻辑上出错。1.2 最深根到底在求什么假设图已经是一棵树了。接下来要理解“最深根”的定义把某个结点r当作根这棵树就有了唯一的高度高度等于从r出发到所有其他结点的最大边数。一个结点是“最深根”意味着以它为根时这个高度最大。注意这里不是问“离某个固定点最远的点”而是问“让整棵树挂起来之后下垂得最长的那个距离达到最大”的根有哪些。这里有一个很重要的直觉如果一棵树里最远的两个结点之间的距离是D即树的直径长度那么以任意结点r为根的高度不可能超过D除非r本身就是某条直径的端点否则它到某个方向上最远点的距离一定小于D。换句话说最深根本质上就是树的直径端点这道题表面上在考“深度”实际上在考“树的直径”。把问题翻译到这一层之后解法路线就清晰了先判断连通连通之后找出树上所有直径端点按编号升序输出。这也是为什么这道题适合拿来练手——它不仅考基础的数据结构还考你能不能把一个看似“高度”的问题重新建模成“直径端点”的问题。2. 连通性先行为什么第一步必须交给并查集2.1 用DFS判断连通为什么不够优雅有的同学会想连通性用一次DFS也能判断从1号点出发如果访问到的结点数等于N不就说明连通了吗这个思路本身没错但它有个局限性当图不连通时题目还要求输出“有几个连通分量”你只靠一次DFS是数不全的必须循环遍历所有未访问结点对每个连通分量各做一次DFS或BFS。代码写下来也不算复杂但整体逻辑会变得分散。相比之下并查集在读边的同时就把合并操作做完了。N-1条边读完之后所有连通信息都已经在并查集里剩下只需统计根的数量即可。更关键的是后续求最深根的两次遍历依然要在“图连通”这个前提下进行。先做好连通性判断能让你在进入树的逻辑之前就明确前提避免写出“图不连通还在求直径”这种结构性错误。2.2 并查集统计连通分量的正确姿势并查集的基本操作不复杂初始化时每个结点的父结点指向自己对每条边的两个端点做Union最后统计一共有多少个集合。但我在第一次写的时候在这里踩了一个隐蔽的坑——直接在Union完成之后数parent[i] i的个数结果在部分结点没有完成路径压缩时统计出的分量数是不对的。正确做法是先对每个结点执行一次findRoot(i)把所有结点都压缩到所在集合的根下方然后再用set去重统计根的数量。setint roots; for (int i 1; i n; i) { roots.insert(findRoot(i)); } int comp roots.size();这一步看着不起眼但如果不做路径压缩就统计遇到链式结构时会数出多于真实数量的“根”。并查集几乎不影响时间复杂度它的均摊开销可以认为是常数级。对这道题来说N最大到10000量级并查集完全可以忽略不计地完成任务。3. 两次DFS的直觉来源从“最远点”到“直径端点”3.1 一个容易被忽略的定理现在进入整道题最核心的部分为什么两次DFS就能找出所有最深根这里依赖一个经典的图论结论在一棵树里从任意结点x出发走到离x最远的结点y那么y一定是某条直径的端点。这个定理的证明是很多教材里的标准内容但我想换一种更直观的方式帮助记忆。树是一种没有环的结构任意两个结点之间的路径是唯一的。可以想象树被一条最长的路径“直径”贯穿直径两端是u和v。现在你站在直径外的任意一点x想找一个离你最远的点那么你找到的点一定是u或v而不可能是直径中间的某个点。原因很简单如果你走到直径中间某个点就停下来了那说明你并没有走到路径的尽头树里没有环可以绕你只有走到直径的端点才能把距离拉满否则一定还有路可以继续往前延伸距离还能更大。这个定理的意义在于第一次DFS的起点可以随便选。从任意起点出发找到的最远结点都是某个直径端点。于是我们有了一个可靠的“锚点”——只要拿到了任意一个直径端点再从它出发找所有最远点就能覆盖到它的“另一侧”端点群。3.2 为什么要取两次结果的并集第一次DFS从任意结点a出发找到所有距离a最远的结点集合S1。第二次DFS从S1中的任意一个结点b出发找到所有距离b最远的结点集合S2。最终答案不是S2而是S1 ∪ S2这一点是很多人容易漏掉的。为什么要并集因为树的直径可能不止一条。一个经典的例子是以一条长链为主干主干两端分别挂着两个分支端点。假设主干左端有端点L1右端有端点R1、R2。从L1出发找最远点得到的不一定是R1和R2全部可能只得到其中一个从R1出发找最远点同样可能只覆盖到左端的一部分端点。两个方向各自找回的“最远点集合”都只是直径端点集合的真子集只有把两次结果合并才能保证一个端点都不漏。更深一层说任意直径端点之间它们的距离都恰好等于树的直径长度。第二次DFS的起点本身是一个直径端点从它出发到任意其他直径端点的距离必然也是直径长度所以任意最远点都会进入S2。反过来第一次DFS得到的S1也不能丢掉因为没有理由证明S1里的点一定包含在S2里。稳妥的策略就是两次结果都保留用set合并去重最后升序输出。4. 实现细节里的四个隐形门槛4.1 N1最孤独的树也是树当N等于1时输入只有结点1没有任何边。用并查集判断连通分量数就是1于是程序会进入求最深根的流程。此时第一次BFS从1出发最远点集合是[1]第二次BFS从1出发最远点集合还是[1]最终输出1逻辑上其实不会出错。但我依然建议在一开始就做一个特判。原因不是逻辑问题而是工程容错如果后面的代码习惯性地认为“树的直径两端至少有两个不同结点”或者某些临时数组按边数初始化N1时就容易出现越界或空输出。我在练习时就见过有人把第一次BFS返回的vector强行当成至少有两个元素来用N1直接崩掉。一行特判能省掉后续无数烦恼if (n 1) { printf(1\n); return 0; }4.2 邻接矩阵直接出局空间账要算清这道题的N上限是10000。如果采用邻接矩阵存储需要开一个10000 × 10000的二维数组也就是一亿个整数。一个int占4字节总内存是400MB左右绝大多数OJ直接内存超限。即使改成bool矩阵一亿个字节也有100MB在内存限制严格的OJ里依然很悬。正确做法是邻接表用vectorvectorint或者链式前向星。树只有N-1条边无向图要双向存总共约2×(N-1)条边记录内存开销小了至少两个数量级。这个选择不是偏好问题而是能不能过题的问题。从空间复杂度角度看邻接矩阵是O(N²)邻接表是O(N)这道题的N设置就是为了逼你放弃矩阵。4.3 递归陷阱DFS深度等于N时会发生什么如果你选择用递归DFS求最远距离在最坏情况下会碰上一个巨大的麻烦当树的形状退化成一条链时从链的一端递归进入另一端递归深度就是N。N10000时递归调用栈需要压入大约一万层。C在部分OJ环境中的默认栈空间约1MB左右一万层递归虽然有时候能勉强通过但并不是所有编译器、所有系统都这么宽容Python则更直接默认递归深度限制是1000超过就抛RecursionError。解决这个问题有两种思路第一把DFS换成BFSBFS用队列存储天然不依赖系统调用栈这也是我最推荐的做法第二保留DFS但改为手工栈或者像Python里那样先sys.setrecursionlimit(200000)把限制调大。不过我已经被坑过一次之后就养成了树上求深度的题目优先用BFS的习惯省心又稳定。4.4 去重与升序最后一个不注意也会全错第一次DFS拿到的最远点集合和第二次DFS拿到的最远点集合完全可能包含重复结点。如果你图省事把两个vector直接拼接后输出同一编号会出现两次。题目要求的是把所有满足条件的根按编号升序输出重复输出会被判定为格式错误或答案错误。我最开始犯的错误是只做了sort没有去重结果结点输出两次WA了一发才反应过来。后来学乖了直接用setint收集S1和S2的全部元素set天然去重且有序最后遍历输出即可。如果你更喜欢vector也可以sort之后接一个unique效果一样。这里没有技术难度纯粹是审题仔细不仔细的问题。5. 可以直接提交的参考实现5.1 C用BFS代替DFS更省心我用BFS实现了最远点集合查找同时在读入边的时候同步做并查集合并整体代码不长。BFS的距离数组用dist记录初始置为-1表示未访问从起点开始逐层扩散。#include bits/stdc.h using namespace std; const int MAXN 10005; vectorint adj[MAXN]; int fa[MAXN]; int findRoot(int x) { if (fa[x] ! x) fa[x] findRoot(fa[x]); return fa[x]; } void unionSet(int a, int b) { a findRoot(a); b findRoot(b); if (a ! b) fa[a] b; } vectorint farthest(int start, int n) { vectorint dist(n 1, -1); queueint q; q.push(start); dist[start] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } int maxd 0; for (int i 1; i n; i) { maxd max(maxd, dist[i]); } vectorint res; for (int i 1; i n; i) { if (dist[i] maxd) res.push_back(i); } return res; } int main() { int n; if (scanf(%d, n) ! 1) return 0; for (int i 1; i n; i) fa[i] i; for (int i 1; i n; i) { int a, b; scanf(%d%d, a, b); adj[a].push_back(b); adj[b].push_back(a); unionSet(a, b); } setint roots; for (int i 1; i n; i) { roots.insert(findRoot(i)); } if (roots.size() 1) { printf(Error: %d components\n, (int)roots.size()); return 0; } vectorint first farthest(1, n); vectorint second farthest(first[0], n); setint ans; for (int x : first) ans.insert(x); for (int x : second) ans.insert(x); for (int x : ans) { printf(%d\n, x); } return 0; }这段代码的核心思路是并查集判断连通连通后取1号点做第一次BFS拿到所有最远点再取其中任意一个点做第二次BFS最后用set合并结果。值得注意的细节是我在第一次BFS返回的vector里取了第一个元素first[0]作为第二次BFS的起点因为first非空是有保证的——至少起点自身就在集合里。5.2 Python用一次性读入和集合去重提高容错率Python版本的逻辑和C完全一致但有几个环境相关的优化点。首先是输入我推荐使用sys.stdin.read().split()一次性读入全部数据再解析而不是逐行readline()在大量测试数据下性能差异明显。其次是BFS使用deque入队出队都是常数时间比用列表模拟队列更稳定。import sys from collections import deque sys.setrecursionlimit(1 25) def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) fa list(range(n 1)) adj [[] for _ in range(n 1)] def find(x): while fa[x] ! x: fa[x] fa[fa[x]] x fa[x] return x def union(a, b): ra, rb find(a), find(b) if ra ! rb: fa[ra] rb idx 1 for _ in range(n - 1): a int(data[idx]) b int(data[idx 1]) idx 2 adj[a].append(b) adj[b].append(a) union(a, b) comp len({find(i) for i in range(1, n 1)}) if comp 1: sys.stdout.write(fError: {comp} components\n) return def bfs(start): dist [-1] * (n 1) dist[start] 0 q deque([start]) while q: u q.popleft() for v in adj[u]: if dist[v] -1: dist[v] dist[u] 1 q.append(v) maxd max(dist[1:]) return [i for i in range(1, n 1) if dist[i] maxd] first bfs(1) second bfs(first[0]) ans sorted(set(first) | set(second)) sys.stdout.write(\n.join(map(str, ans))) if __name__ __main__: main()这里我用了路径压缩的find写法用循环替代递归避免find本身的递归深度问题。comp统计用了集合推导式把每个find(i)的结果去重代码很简洁。Python版本在N10000时表现完全没问题运行时间通常低于OJ限制。6. 做完这题后值得顺手带走的三个套路6.1 树上最远点问题的一次性迁移“两次遍历找直径端点”这套方法适用范围很广。以后遇到类似题目比如“求树中距离最远的一对结点之间的距离”“判断某个结点是否位于某条直径上”“输出所有直径覆盖的结点”核心思路都可以直接迁移任取一点找最远点再从最远点出发找所有最远点必要时合并两次端点集合。但要注意适用范围这个套路只在无权树上成立。如果题目变成带权边或者求的不是最远距离而是带约束的最优路径两次DFS就会失效需要换树形DP或Dijkstra一类的方案。判断的标准很简单路径长度是否由“边数”决定如果是那么两次遍历依然是首选。6.2 什么时候该把递归改成迭代Deepest Root这道题给了我一个很好的教训递归深度是一个不能赌的东西。不同OJ的栈空间设置不一样编译器优化也不一样同样的代码在本地测试通过提交上去也可能栈溢出。我的建议是一旦预估递归深度可能达到数千层以上就主动切换到BFS或手工栈不要等到爆栈之后再修改。判断方法很简单如果问题的遍历结构是一棵可能退化成链的树而N是万级甚至百万级递归就是一个风险因素。BFS不是面试或考试中“低人一等”的方案它往往更稳代码也不难写。6.3 从两次DFS到树形DP的边界在哪最后想聊一个进阶话题。两次DFS的写法很优雅但它不能处理带权直径这时候需要树形DP。树形DP求带权直径的核心思路是对每个结点维护从该结点向下到子树某个叶子的最大距离和次大距离两者相加就能得到“经过该结点的最长路径”。一次DFS后全局最大值就是树的带权直径。这个套路和两次DFS的适用场景正好互补。当你看到“每条边有权求最远距离”时第一反应不要再是两次DFS而是树形DP。反过来看到“边数为1求所有最深根”两次DFS依然是最短平快的解法。把这两种方法的边界在脑子里划清楚遇到新题时定位算法的速度会快很多。最后再分享一个我自己的判断习惯看到“N个点、N-1条边”第一反应就是树看到“输出所有满足条件的根节点”立刻想到树的直径端点看到“先判断是否连通”默认用并查集。这套反射建立起来之后这类树形题基本都能在几分钟内锁定正确方向。 
长河君 · 2026/10/17 9:52:19 · 阅读 1.2k PAT甲级A1021：用并查集判连通，两次DFS找树直径端点
PAT甲级里做过的图论题不少但是A1021 Deepest Root是少数几道我做完之后又专门回头复盘了一整晚的题。表面上看它只是让你在一棵树上找几个深度最大的点真写起来才发现判断连通性、找树的直径端点、处理单节点的边界几乎每一步都藏着扣分点。这篇文章不只是贴一份能AC的代码我想把题面背后的图论模型、两次DFS为什么成立、以及我实际提交过程中踩到的坑一起讲清楚。如果你是正在准备PAT甲级的考生或者正在练树与图的算法题这篇文章应该能帮你省下不少来回查资料和反复提交的时间。1. 题面读三遍之后我发现它真正考的是三件事1.1 N个结点、N-1条边这个描述藏了什么先还原题目的原始样貌给定N个结点和N-1条边每个结点编号从1到N边是无向的。题目要求先判断这个图是不是一棵树如果它不是树输出它有多少个连通分量如果它是树就找出所有“最深根”——即以该结点为根时整棵树的高度能达到最大值。很多人的第一反应是这不就是做一遍DFS求高度吗但仔细想题目给了N个点、N-1条边这个数量关系本身就是一个强烈的信号。对于无向简单图N个点、N-1条边、并且连通等价于它是一棵树。为什么因为在一个连通图里任意生成树恰好有N-1条边如果这个图有N-1条边且仍然连通它就不能再删掉任何一条边而不破坏连通性于是不能有环只能是树本身。换句话说判断“是不是树”其实只需要回答一个问题这个图连通吗连通就是树不连通就输出连通分量个数。这个转化是所有后续步骤的地基可惜很多人一上来就去计算深度完全没有意识到第一步应该是连通性判断。一旦图不连通DFS返回的深度数据就是局部信息没有任何全局意义代码写得再漂亮也会在逻辑上出错。1.2 最深根到底在求什么假设图已经是一棵树了。接下来要理解“最深根”的定义把某个结点r当作根这棵树就有了唯一的高度高度等于从r出发到所有其他结点的最大边数。一个结点是“最深根”意味着以它为根时这个高度最大。注意这里不是问“离某个固定点最远的点”而是问“让整棵树挂起来之后下垂得最长的那个距离达到最大”的根有哪些。这里有一个很重要的直觉如果一棵树里最远的两个结点之间的距离是D即树的直径长度那么以任意结点r为根的高度不可能超过D除非r本身就是某条直径的端点否则它到某个方向上最远点的距离一定小于D。换句话说最深根本质上就是树的直径端点这道题表面上在考“深度”实际上在考“树的直径”。把问题翻译到这一层之后解法路线就清晰了先判断连通连通之后找出树上所有直径端点按编号升序输出。这也是为什么这道题适合拿来练手——它不仅考基础的数据结构还考你能不能把一个看似“高度”的问题重新建模成“直径端点”的问题。2. 连通性先行为什么第一步必须交给并查集2.1 用DFS判断连通为什么不够优雅有的同学会想连通性用一次DFS也能判断从1号点出发如果访问到的结点数等于N不就说明连通了吗这个思路本身没错但它有个局限性当图不连通时题目还要求输出“有几个连通分量”你只靠一次DFS是数不全的必须循环遍历所有未访问结点对每个连通分量各做一次DFS或BFS。代码写下来也不算复杂但整体逻辑会变得分散。相比之下并查集在读边的同时就把合并操作做完了。N-1条边读完之后所有连通信息都已经在并查集里剩下只需统计根的数量即可。更关键的是后续求最深根的两次遍历依然要在“图连通”这个前提下进行。先做好连通性判断能让你在进入树的逻辑之前就明确前提避免写出“图不连通还在求直径”这种结构性错误。2.2 并查集统计连通分量的正确姿势并查集的基本操作不复杂初始化时每个结点的父结点指向自己对每条边的两个端点做Union最后统计一共有多少个集合。但我在第一次写的时候在这里踩了一个隐蔽的坑——直接在Union完成之后数parent[i] i的个数结果在部分结点没有完成路径压缩时统计出的分量数是不对的。正确做法是先对每个结点执行一次findRoot(i)把所有结点都压缩到所在集合的根下方然后再用set去重统计根的数量。setint roots; for (int i 1; i n; i) { roots.insert(findRoot(i)); } int comp roots.size();这一步看着不起眼但如果不做路径压缩就统计遇到链式结构时会数出多于真实数量的“根”。并查集几乎不影响时间复杂度它的均摊开销可以认为是常数级。对这道题来说N最大到10000量级并查集完全可以忽略不计地完成任务。3. 两次DFS的直觉来源从“最远点”到“直径端点”3.1 一个容易被忽略的定理现在进入整道题最核心的部分为什么两次DFS就能找出所有最深根这里依赖一个经典的图论结论在一棵树里从任意结点x出发走到离x最远的结点y那么y一定是某条直径的端点。这个定理的证明是很多教材里的标准内容但我想换一种更直观的方式帮助记忆。树是一种没有环的结构任意两个结点之间的路径是唯一的。可以想象树被一条最长的路径“直径”贯穿直径两端是u和v。现在你站在直径外的任意一点x想找一个离你最远的点那么你找到的点一定是u或v而不可能是直径中间的某个点。原因很简单如果你走到直径中间某个点就停下来了那说明你并没有走到路径的尽头树里没有环可以绕你只有走到直径的端点才能把距离拉满否则一定还有路可以继续往前延伸距离还能更大。这个定理的意义在于第一次DFS的起点可以随便选。从任意起点出发找到的最远结点都是某个直径端点。于是我们有了一个可靠的“锚点”——只要拿到了任意一个直径端点再从它出发找所有最远点就能覆盖到它的“另一侧”端点群。3.2 为什么要取两次结果的并集第一次DFS从任意结点a出发找到所有距离a最远的结点集合S1。第二次DFS从S1中的任意一个结点b出发找到所有距离b最远的结点集合S2。最终答案不是S2而是S1 ∪ S2这一点是很多人容易漏掉的。为什么要并集因为树的直径可能不止一条。一个经典的例子是以一条长链为主干主干两端分别挂着两个分支端点。假设主干左端有端点L1右端有端点R1、R2。从L1出发找最远点得到的不一定是R1和R2全部可能只得到其中一个从R1出发找最远点同样可能只覆盖到左端的一部分端点。两个方向各自找回的“最远点集合”都只是直径端点集合的真子集只有把两次结果合并才能保证一个端点都不漏。更深一层说任意直径端点之间它们的距离都恰好等于树的直径长度。第二次DFS的起点本身是一个直径端点从它出发到任意其他直径端点的距离必然也是直径长度所以任意最远点都会进入S2。反过来第一次DFS得到的S1也不能丢掉因为没有理由证明S1里的点一定包含在S2里。稳妥的策略就是两次结果都保留用set合并去重最后升序输出。4. 实现细节里的四个隐形门槛4.1 N1最孤独的树也是树当N等于1时输入只有结点1没有任何边。用并查集判断连通分量数就是1于是程序会进入求最深根的流程。此时第一次BFS从1出发最远点集合是[1]第二次BFS从1出发最远点集合还是[1]最终输出1逻辑上其实不会出错。但我依然建议在一开始就做一个特判。原因不是逻辑问题而是工程容错如果后面的代码习惯性地认为“树的直径两端至少有两个不同结点”或者某些临时数组按边数初始化N1时就容易出现越界或空输出。我在练习时就见过有人把第一次BFS返回的vector强行当成至少有两个元素来用N1直接崩掉。一行特判能省掉后续无数烦恼if (n 1) { printf(1\n); return 0; }4.2 邻接矩阵直接出局空间账要算清这道题的N上限是10000。如果采用邻接矩阵存储需要开一个10000 × 10000的二维数组也就是一亿个整数。一个int占4字节总内存是400MB左右绝大多数OJ直接内存超限。即使改成bool矩阵一亿个字节也有100MB在内存限制严格的OJ里依然很悬。正确做法是邻接表用vectorvectorint或者链式前向星。树只有N-1条边无向图要双向存总共约2×(N-1)条边记录内存开销小了至少两个数量级。这个选择不是偏好问题而是能不能过题的问题。从空间复杂度角度看邻接矩阵是O(N²)邻接表是O(N)这道题的N设置就是为了逼你放弃矩阵。4.3 递归陷阱DFS深度等于N时会发生什么如果你选择用递归DFS求最远距离在最坏情况下会碰上一个巨大的麻烦当树的形状退化成一条链时从链的一端递归进入另一端递归深度就是N。N10000时递归调用栈需要压入大约一万层。C在部分OJ环境中的默认栈空间约1MB左右一万层递归虽然有时候能勉强通过但并不是所有编译器、所有系统都这么宽容Python则更直接默认递归深度限制是1000超过就抛RecursionError。解决这个问题有两种思路第一把DFS换成BFSBFS用队列存储天然不依赖系统调用栈这也是我最推荐的做法第二保留DFS但改为手工栈或者像Python里那样先sys.setrecursionlimit(200000)把限制调大。不过我已经被坑过一次之后就养成了树上求深度的题目优先用BFS的习惯省心又稳定。4.4 去重与升序最后一个不注意也会全错第一次DFS拿到的最远点集合和第二次DFS拿到的最远点集合完全可能包含重复结点。如果你图省事把两个vector直接拼接后输出同一编号会出现两次。题目要求的是把所有满足条件的根按编号升序输出重复输出会被判定为格式错误或答案错误。我最开始犯的错误是只做了sort没有去重结果结点输出两次WA了一发才反应过来。后来学乖了直接用setint收集S1和S2的全部元素set天然去重且有序最后遍历输出即可。如果你更喜欢vector也可以sort之后接一个unique效果一样。这里没有技术难度纯粹是审题仔细不仔细的问题。5. 可以直接提交的参考实现5.1 C用BFS代替DFS更省心我用BFS实现了最远点集合查找同时在读入边的时候同步做并查集合并整体代码不长。BFS的距离数组用dist记录初始置为-1表示未访问从起点开始逐层扩散。#include bits/stdc.h using namespace std; const int MAXN 10005; vectorint adj[MAXN]; int fa[MAXN]; int findRoot(int x) { if (fa[x] ! x) fa[x] findRoot(fa[x]); return fa[x]; } void unionSet(int a, int b) { a findRoot(a); b findRoot(b); if (a ! b) fa[a] b; } vectorint farthest(int start, int n) { vectorint dist(n 1, -1); queueint q; q.push(start); dist[start] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } int maxd 0; for (int i 1; i n; i) { maxd max(maxd, dist[i]); } vectorint res; for (int i 1; i n; i) { if (dist[i] maxd) res.push_back(i); } return res; } int main() { int n; if (scanf(%d, n) ! 1) return 0; for (int i 1; i n; i) fa[i] i; for (int i 1; i n; i) { int a, b; scanf(%d%d, a, b); adj[a].push_back(b); adj[b].push_back(a); unionSet(a, b); } setint roots; for (int i 1; i n; i) { roots.insert(findRoot(i)); } if (roots.size() 1) { printf(Error: %d components\n, (int)roots.size()); return 0; } vectorint first farthest(1, n); vectorint second farthest(first[0], n); setint ans; for (int x : first) ans.insert(x); for (int x : second) ans.insert(x); for (int x : ans) { printf(%d\n, x); } return 0; }这段代码的核心思路是并查集判断连通连通后取1号点做第一次BFS拿到所有最远点再取其中任意一个点做第二次BFS最后用set合并结果。值得注意的细节是我在第一次BFS返回的vector里取了第一个元素first[0]作为第二次BFS的起点因为first非空是有保证的——至少起点自身就在集合里。5.2 Python用一次性读入和集合去重提高容错率Python版本的逻辑和C完全一致但有几个环境相关的优化点。首先是输入我推荐使用sys.stdin.read().split()一次性读入全部数据再解析而不是逐行readline()在大量测试数据下性能差异明显。其次是BFS使用deque入队出队都是常数时间比用列表模拟队列更稳定。import sys from collections import deque sys.setrecursionlimit(1 25) def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) fa list(range(n 1)) adj [[] for _ in range(n 1)] def find(x): while fa[x] ! x: fa[x] fa[fa[x]] x fa[x] return x def union(a, b): ra, rb find(a), find(b) if ra ! rb: fa[ra] rb idx 1 for _ in range(n - 1): a int(data[idx]) b int(data[idx 1]) idx 2 adj[a].append(b) adj[b].append(a) union(a, b) comp len({find(i) for i in range(1, n 1)}) if comp 1: sys.stdout.write(fError: {comp} components\n) return def bfs(start): dist [-1] * (n 1) dist[start] 0 q deque([start]) while q: u q.popleft() for v in adj[u]: if dist[v] -1: dist[v] dist[u] 1 q.append(v) maxd max(dist[1:]) return [i for i in range(1, n 1) if dist[i] maxd] first bfs(1) second bfs(first[0]) ans sorted(set(first) | set(second)) sys.stdout.write(\n.join(map(str, ans))) if __name__ __main__: main()这里我用了路径压缩的find写法用循环替代递归避免find本身的递归深度问题。comp统计用了集合推导式把每个find(i)的结果去重代码很简洁。Python版本在N10000时表现完全没问题运行时间通常低于OJ限制。6. 做完这题后值得顺手带走的三个套路6.1 树上最远点问题的一次性迁移“两次遍历找直径端点”这套方法适用范围很广。以后遇到类似题目比如“求树中距离最远的一对结点之间的距离”“判断某个结点是否位于某条直径上”“输出所有直径覆盖的结点”核心思路都可以直接迁移任取一点找最远点再从最远点出发找所有最远点必要时合并两次端点集合。但要注意适用范围这个套路只在无权树上成立。如果题目变成带权边或者求的不是最远距离而是带约束的最优路径两次DFS就会失效需要换树形DP或Dijkstra一类的方案。判断的标准很简单路径长度是否由“边数”决定如果是那么两次遍历依然是首选。6.2 什么时候该把递归改成迭代Deepest Root这道题给了我一个很好的教训递归深度是一个不能赌的东西。不同OJ的栈空间设置不一样编译器优化也不一样同样的代码在本地测试通过提交上去也可能栈溢出。我的建议是一旦预估递归深度可能达到数千层以上就主动切换到BFS或手工栈不要等到爆栈之后再修改。判断方法很简单如果问题的遍历结构是一棵可能退化成链的树而N是万级甚至百万级递归就是一个风险因素。BFS不是面试或考试中“低人一等”的方案它往往更稳代码也不难写。6.3 从两次DFS到树形DP的边界在哪最后想聊一个进阶话题。两次DFS的写法很优雅但它不能处理带权直径这时候需要树形DP。树形DP求带权直径的核心思路是对每个结点维护从该结点向下到子树某个叶子的最大距离和次大距离两者相加就能得到“经过该结点的最长路径”。一次DFS后全局最大值就是树的带权直径。这个套路和两次DFS的适用场景正好互补。当你看到“每条边有权求最远距离”时第一反应不要再是两次DFS而是树形DP。反过来看到“边数为1求所有最深根”两次DFS依然是最短平快的解法。把这两种方法的边界在脑子里划清楚遇到新题时定位算法的速度会快很多。最后再分享一个我自己的判断习惯看到“N个点、N-1条边”第一反应就是树看到“输出所有满足条件的根节点”立刻想到树的直径端点看到“先判断是否连通”默认用并查集。这套反射建立起来之后这类树形题基本都能在几分钟内锁定正确方向。