如果你的机考题单里出现“找城市”这三个字第一眼千万别被“城市”“道路”这两个词带跑。我第一次做这一类题目时下意识就开始想最短路、多源 BFS甚至往最小生成树上靠结果把简单问题复杂化了。后来仔细读题才反应过来题目给的是 n 个城市和 n-1 条道路并且任意两个城市之间有且仅有一条路径这分明就是一棵树。这道题挂 200 分的分值看起来唬人实际上思路一旦转过来实现量并不大。它考察的是树结构里很经典的一个结论——树的重心centroid只是换了层“城市网络”的包装。这篇文章我会把题面拆开、把推导过程讲透然后分别给出 Java、C、Python、JS 四种语言的完整实现最后聊几个我在实际测试中踩过的坑。无论你是在准备机考还是想补一下树形 DP 的基础这篇都值得看完。1. 题面拆解这个“找城市”其实是在找树的重心1.1 三个关键条件先圈出来“找城市”这类题目的题面通常长这样有 n 个城市城市编号从 1 到 n城市之间由 n-1 条道路连接。任意两个城市之间有且仅有一条路径可达。现在要选择一个城市作为中心要求这个城市失联后剩余城市会按照原有道路自然分成若干个连通区域我们希望这些区域中“最大的那个区域”包含的城市数尽可能少。读题时有三句话必须圈出来第一n 个城市、n-1 条道路。边数恰好等于顶点数减一这是树的一个标志性特征。第二任意两个城市之间有且仅有一条路径。这句话等价于“图是连通且无环的”连通无环就是树。第三要让“最大连通块”尽可能小。这是典型的“最坏情况最小化”问题在树上恰好对应重心的定义。有些变体还会在题目里说“如果有多个满足条件的城市输出编号最小的”或者“按编号升序输出全部满足条件的城市”这个细节直接影响输出逻辑后面讲代码时会单独说。1.2 “删掉节点后最大连通块最小”到底怎么理解想象一棵树你从中间摘掉一个节点这个节点原本连接着若干条边。由于树没有环摘掉它之后每一条边连接的“那一头”都会各自形成一个独立的连通块。举个例子一个节点连着三个儿子删掉它之后三个儿子各自带着自己的子树分成三块。如果这个节点还有一个父节点那么父节点方向也会形成第四块。题目要求的是摘掉哪个节点能让这些块中“最大的一块”尽量小。注意不是让块数最多也不是让总路径最短而是单纯的“最严重的那块别太大”。这种均衡性的要求在现实中也很有场景感比如灾备中心选址、分布式系统中选取控制节点都希望某个节点故障后剩下的网络不至于有一大片完全失联。在树结构里满足“删除后最大连通块最小”的节点就是这颗树的重心。一棵树的重心最多有两个如果有两个它们相邻。所以这道题本质上考的就是重心查找只不过用城市网络做了一层包装。1.3 为什么一眼能看出是树而不是普通图有读者可能会问如果题目不保证“任意两个城市之间有且仅有一条路径”只是给 n 个点和 m 条边那这题还能这么做吗答案是不能。普通图里删掉一个点之后剩下多少个连通块、每个块多大需要先求割点、再跑连通分量复杂度会明显上升代码量也完全不是一个级别。所以“任意两个城市有且仅有一条路径”这个条件是整道题的分水岭。它直接告诉你别想复杂了这就是树。做题时先把模型识别出来比急着写代码重要得多。很多人在这一步被“城市网络”四个字带偏跑去套最短路径模板白白浪费时间。2. 算法推导一次DFS算出所有候选值2.1 子树规模数组 sz 的求法识别出是树之后算法非常固定。随便选一个节点作为根这里我习惯选 1 号城市。从根开始做一次深度优先搜索DFS统计出每个节点的子树大小记作 sz[u]含义是以 u 为根的子树里一共有多少个节点。递归过程很简单先把 sz[u] 初始化为 1自己算一个然后遍历所有邻接点跳过父节点递归处理子节点再把子节点的 sz 累加到 sz[u] 上。这一步的时间复杂度是 O(n)因为每条边只会被访问两次。之所以能“任选一个根”是因为树本身没有方向。固定根只是给 DFS 一个遍历的起点并不会改变“删除某个节点后树被分成几块”这个事实。换个根sz 数组的值会变但最后算出来的“最大块”不会变。2.2 删除任意节点后的最大块公式一侧是父边一侧全是子树假设现在要删除节点 u那么树会被分成两部分来源第一部分是 u 的每个儿子各自带着的子树。如果 u 有儿子 v1、v2、v3那么这些部分的大小分别就是 sz[v1]、sz[v2]、sz[v3]。第二部分是 u 的“父方向”。以 1 为根来 DFS 时除了根节点以外每个节点都有一个指向父节点的边。删掉 u 之后父节点那一侧的剩余节点数是多少整个树一共有 n 个节点u 的子树占了 sz[u] 个剩下的 n - sz[u] 个就都在父方向那一侧。所以删除 u 之后最大的连通块大小就是maxPart[u] max( max(sz[v]) , n - sz[u] )其中 v 遍历 u 的所有儿子。对于根节点来说n - sz[root] 0父方向为空只需要看各个儿子的子树大小。这个公式是整个题目的核心。一旦想明白剩下的就是遍历 u 1 到 n把每个节点的 maxPart 算出来取其中最小的那个。2.3 多解与输出规则一个手算例子树的重心可能有多个多数题目要求输出编号最小的那一个。这种情况下只需要在遍历时维护一个全局最优值 best遇到 maxPart 更小的节点就更新答案遇到 maxPart 等于 best 的节点看编号是否更小是则更新。如果题目要求输出全部重心就把 ans 改成一个数组相等时追加进去最后统一输出。我用手算一个例子验证。假设 n 6边是1-2、1-3、2-4、2-5、3-6。以 1 为根 DFS 得到sz[4] 1sz[5] 1sz[6] 1sz[2] 3sz[3] 2sz[1] 6逐个节点算节点删除后各块大小最大块1子树块 3、2父侧 032子树块 1、1父侧 6-3333子树块 1父侧 6-2444无子树父侧 555无子树父侧 556无子树父侧 55最小最大块为 3对应的节点是 1 和 2。如果题目要求输出最小编号答案就是 1如果要求输出全部就输出“1 2”。3. Java与C的落地方案邻接表存储与递归DFS3.1 Java代码集合邻接表与递归统计Java 里最直观的写法是用 List [] 作为邻接表。为什么不建议用二维矩阵因为 n 如果到 10^5矩阵需要 10^10 个格子内存直接爆炸。邻接表只存实际存在的边n 个点、2(n-1) 条边不会浪费空间。这里我给出递归实现的版本代码简洁适合 n 在 10^4 量级的场景。如果你确认题目 n 可能到 10^5 且存在链状数据建议再往下看第 4 节的迭代思路把递归改成显式栈。import java.util.*; public class Main { static int n; static ListInteger[] g; static int[] sz; static void dfs(int u, int parent) { sz[u] 1; for (int v : g[u]) { if (v parent) continue; dfs(v, u); sz[u] sz[v]; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); n sc.nextInt(); g new ArrayList[n 1]; for (int i 1; i n; i) { g[i] new ArrayList(); } for (int i 0; i n - 1; i) { int a sc.nextInt(); int b sc.nextInt(); g[a].add(b); g[b].add(a); } sz new int[n 1]; dfs(1, 0); int best n; int ans n 1; for (int u 1; u n; u) { int maxPart n - sz[u]; for (int v : g[u]) { if (sz[v] sz[u]) { maxPart Math.max(maxPart, sz[v]); } } if (maxPart best) { best maxPart; ans u; } else if (maxPart best u ans) { ans u; } } System.out.println(ans); } }3.2 C代码数组模拟邻接表性能优先C 语言里用数组模拟邻接表是标准做法。head[u] 存的是 u 的第一条边的下标to[e] 存边的终点nxt[e] 存同一起点的下一条边的下标edgeCnt 记录当前边数量。每次加边要加两条u 到 v 和 v 到 u。这种写法的好处是内存连续、访问速度快而且不依赖任何动态分配在 OJ 上性能很稳定。缺点是理解起来比 vector 稍微绕一点但用习惯了其实非常顺手。#include stdio.h #define MAXN 200005 int head[MAXN], to[MAXN 1], nxt[MAXN 1], edgeCnt; int sz[MAXN], n; void addEdge(int u, int v) { to[edgeCnt] v; nxt[edgeCnt] head[u]; head[u] edgeCnt; } void dfs(int u, int parent) { sz[u] 1; for (int e head[u]; e; e nxt[e]) { int v to[e]; if (v parent) continue; dfs(v, u); sz[u] sz[v]; } } int main() { scanf(%d, n); for (int i 0; i n - 1; i) { int a, b; scanf(%d%d, a, b); addEdge(a, b); addEdge(b, a); } dfs(1, 0); int best n, ans n 1; for (int u 1; u n; u) { int maxPart n - sz[u]; for (int e head[u]; e; e nxt[e]) { int v to[e]; if (sz[v] sz[u] sz[v] maxPart) { maxPart sz[v]; } } if (maxPart best) { best maxPart; ans u; } else if (maxPart best u ans) { ans u; } } printf(%d\n, ans); return 0; }3.3 用 sz[v] sz[u] 判断父子关系的原理与坑细心的读者会发现上面两段代码在第二次遍历时都没有用 parent 数组而是靠“sz[v] sz[u]”来判断 v 是不是 u 的儿子。这个判断是成立的前提是 DFS 以 1 为根完成。解释一下在以 1 为根 DFS 后任何一个非根节点 u它的父节点 p 的整棵子树一定包含 u 的子树所以 sz[p] sz[u]。反过来u 的所有儿子 v它们的子树是 u 的子集所以 sz[v] sz[u]。因此在遍历 u 的所有邻居时只要满足 sz[v] sz[u]v 就一定是 u 的儿子可以放心参与 maxPart 的计算。这个技巧能帮你省掉一个 parent 数组在 C 语言里还能省一点内存。但要注意它依赖“以 1 为根”这个前提如果你的 DFS 根固定为别的节点整个逻辑依然成立只要全程序保持一致就行。4. Python与JS的落地方案显式栈解决深层递归4.1 Python递归版与setrecursionlimit的真相Python 写树形题最容易踩的坑就是递归深度。Python 默认递归深度只有 1000 层左右很多人第一反应是疯狂调大 sys.setrecursionlimit比如设成 10^6。但这里有个误解setrecursionlimit 只是放宽了 Python 解释器的检查限制实际程序仍然跑在 C 的调用栈上。一旦树的形状是一条长链n 100000递归深度就是 100000 层哪怕 setrecursionlimit 设得再大大概率也会直接报段错误Segmentation fault。所以在 Python 里我建议直接一步到位用显式栈做 DFS。这样既绕开递归深度问题又不用依赖编译器或 OJ 的栈大小设置。4.2 Python显式栈版先序收集、逆序累加显式栈的思路和递归不一样它分成两趟第一趟用栈模拟 DFS 的“先序”访问顺序。从根节点 1 出发弹出一个节点就加入 order 列表同时把所有未访问的子节点压入栈。因为树保证无环用一个 parent 数组记录每个节点是从谁那里走过来的就足够不需要额外的 visited 标记。第二趟倒序遍历 order。为什么要倒序因为先序顺序里父节点永远在子节点之前倒序之后每个子节点一定比它的所有后代更早被处理。这样在累加 sz 时每个节点的 sz 都已经包含了全部子树的规模顺序天然正确。import sys def main(): data sys.stdin.buffer.read().split() if not data: return it iter(data) n int(next(it)) g [[] for _ in range(n 1)] for _ in range(n - 1): a int(next(it)) b int(next(it)) g[a].append(b) g[b].append(a) parent [0] * (n 1) parent[1] -1 order [] stack [1] while stack: u stack.pop() order.append(u) for v in g[u]: if v parent[u]: continue parent[v] u stack.append(v) sz [1] * (n 1) for u in reversed(order): for v in g[u]: if v ! parent[u]: sz[u] sz[v] best n ans [] for u in range(1, n 1): max_part n - sz[u] for v in g[u]: if v ! parent[u] and sz[v] max_part: max_part sz[v] if max_part best: best max_part ans [u] elif max_part best: ans.append(u) print( .join(map(str, ans))) if __name__ __main__: main()这段代码输出的是全部重心用空格隔开。如果题目只要求输出最小编号把 ans 改成单变量保存即可逻辑参考第 3 节 Java 版。4.3 JS迭代栈实现与常见入参问题JavaScript 在 Node.js 环境里的递归深度也有限制默认大约一万层左右。n 一旦到 10^5递归方式基本必爆所以 JS 也走显式栈路线。代码结构和 Python 版几乎一一对应只是语法差异。读取输入这里有个容易踩的坑不同 OJ 的 Node 环境支持的输入读取方式不一样。比较通用的是 fs.readFileSync(0, utf8)它读取标准输入文件描述符 0在大多数 OJ 上都能工作。解析时用正则 split(/\s/) 处理空白符就行。const fs require(fs); const input fs.readFileSync(0, utf8).trim().split(/\s/); let ptr 0; const n Number(input[ptr]); const g Array.from({ length: n 1 }, () []); for (let i 0; i n - 1; i) { const a Number(input[ptr]); const b Number(input[ptr]); g[a].push(b); g[b].push(a); } const parent new Array(n 1).fill(0); const order []; const stack [1]; parent[1] -1; while (stack.length) { const u stack.pop(); order.push(u); for (const v of g[u]) { if (v parent[u]) continue; parent[v] u; stack.push(v); } } const sz new Array(n 1).fill(1); for (let i order.length - 1; i 0; i--) { const u order[i]; let total 1; for (const v of g[u]) { if (v ! parent[u]) total sz[v]; } sz[u] total; } let best n; let ans []; for (let u 1; u n; u) { let maxPart n - sz[u]; for (const v of g[u]) { if (v ! parent[u] sz[v] maxPart) maxPart sz[v]; } if (maxPart best) { best maxPart; ans [u]; } else if (maxPart best) { ans.push(u); } } console.log(ans.join( ));4.4 四种实现横向对比语言图的存储方式遍历方式主要风险适用场景JavaArrayList 邻接表递归 DFS深链时递归栈溢出常规数据量C数组邻接表递归 DFS深链时看 OJ 栈大小追求性能推荐Pythonlist 邻接表显式栈 DFS递归深度限制必用迭代稳妥JS数组邻接表显式栈 DFS默认递归深度约一万必用迭代稳妥时间复杂度全部是 O(n)空间复杂度全部是 O(n)。区别主要在于递归深度风险和代码风格的取舍。如果让我建议一个“一套代码打天下”的版本那就是第 4 节的显式栈思路它不依赖语言运行时对递归的宽容度Java、C、Python、JS 都能平移过去。5. 边界用例与实战经验这些坑真的会考5.1 边界用例单节点、链状树、星形树写代码之前先想几个极端数据能帮你避免低级错误。第一个是 n 1。此时没有任何边删除唯一城市后剩下的连通块大小是 0最大块为 0答案就是城市 1。上面的代码要不要特判不需要。g[1] 为空列表DFS 只访问节点 1sz[1] 1。第二次遍历时 maxPart n - sz[1] 0best 初始是 n 10 1所以 ans 1逻辑自然正确。第二个是链状树也就是 n 个节点串成一条线。比如 1-2-3-4-5-6-7这种数据会直接考验递归深度。如果你的代码用的是递归 DFS而 OJ 没有加大栈空间极端情况下会崩。这也是我为什么在 Python 和 JS 里坚持用显式栈的原因。第三个是星形树。中心节点 1 连着 2 到 n 的所有节点。删除中心后剩下 n-1 个孤立点最大块大小为 1这是绝对最优解。任何叶子节点删除后剩下 n-1 个节点会连成一整块最大块为 n-1非常差。所以星形树的重心必然是中心节点。这种用例用来验证代码很合适。5.2 一个链状树的手工验证拿一条 7 节点的链1-2-3-4-5-6-7我们手工推一下看看重心应该落在哪。以 1 为根 DFS 后sz[7]1sz[6]2sz[5]3sz[4]4sz[3]5sz[2]6sz[1]7。逐个算删除后的最大块节点 4左侧是 1-2-3共 3 个节点右侧是 5-6-7共 3 个节点。maxPart 3。节点 3左侧 1-2 共 2 个节点右侧 4-5-6-7 共 4 个节点。maxPart 4。节点 5左侧 1-2-3-4 共 4 个节点右侧 6-7 共 2 个节点。maxPart 4。很明显节点 4 是最优解最大块为 3。这符合我们的直觉一条链的重心在正中间。如果链长为偶数比如 6 个节点 1-2-3-4-5-6节点 3 和 4 会同时满足条件最大块都是 3。这时题目如果只让输出编号最小的就输出 3如果输出全部就输出“3 4”。5.3 实战中容易忽略的三件事第一件是输出规则。我见过不少人代码逻辑全对结果在输出上栽跟头。有些题目要求“如果有多个输出编号最小的”有些要求“按编号从小到大输出所有候选城市”。写代码之前先把这一句圈出来决定 ans 是单变量还是数组。如果是全部输出最后记得 join 时不要有多余空格比如 Python 里用 .join(map(str, ans))JS 里用 ans.join( ) 都能自然处理。第二件是数组下标。城市编号从 1 开始所以所有数组都要开 n 1。如果从 0 开始开遍历时会漏掉节点 n更麻烦的是访问到 g[0] 这个不存在的桶导致空指针或越界。这个错误非常隐蔽因为小数据时可能碰巧能跑对大数据一上就崩。第三件是递归深度。第 3 节的 Java 和 C 版本用的是递归常规数据没问题。但如果题目数据里存在 10^5 级别的链状结构Java 的递归大概率会爆栈C 也要看 OJ 给的栈空间。不想赌运气的话建议直接用第 4 节的显式栈框架把 DFS 改成“先序收集 逆序累加”四个语言通用完全不受递归深度约束。5.4 从这道题延伸出去树形 DP 的基本功“找城市”本质上是一道非常典型的树形 DP 启蒙题。它的核心是计算子树规模然后在每个节点上做一个“合并信息”的操作——这里的信息就是各个子树的大小。这个套路稍加变形就能套到很多题目里比如“删除一个节点后使最长路径最短”“树的最大独立集”“树的直径”等等。我自己的体会是不要只背代码要把“选根 - DFS 统计子树 - 在节点上做决策”这个三段式流程记下来。以后遇到任何树上的最优化问题第一反应都应该是这个框架。尤其是显式栈那套“先序收集、逆序累加”的写法我后来做其他树形题也一直在用完全不依赖递归调试起来还比递归容易打断点观察状态。如果你在机考现场碰到“找城市”能画出树、能写出 sz 数组、能把删除后的最大块公式列出来这道 200 分基本就已经到手了。剩下的就是把代码敲熟。