企业官网建设流程全解析

上周在群里看到有人讨论一道机试第二题，分值200，名字特别朴实，叫“找城市”。我一开始也以为是个图论搜索或者模拟题，结果把输入输出看完之后发现，本质是一道非常典型的树形结构统计题，核心模型就是“树的重心”。这道题能用 Java、JS、Python、C 四门语言做，说明出题人考察的重点不在某个语言特性上，而在你能否把题意翻译成数据结构，然后用一次遍历把答案算出来。这篇就把整个推导过程、四语言实现和我在实际提交里踩过的坑完整写一遍，适合准备大厂机试、笔试，或者想巩固树结构基础的人参考。

1. 先搞懂题意：“找城市”到底在找什么

1.1 题干里的隐藏条件：N个城市、N-1条路

很多人在机试现场看到“城市”“道路”这类词，第一反应是往最短路、最小生成树、并查集方向想，这个直觉在部分题目里是对的，但这道题的关键恰恰在于题目给了一个非常特殊的约束：一共 N 个城市，N-1 条道路，而且整个图是连通的。

这里有个在图论里非常基础但笔试时很容易忽略的结论：一个连通无向图，如果有 N 个节点和 N-1 条边，那它一定是一棵树，没有环。不需要题目明说“无环”，因为数学上已经锁死了。既然是一棵树，那么题目里所有“城市”和“道路”的本质就是“节点”和“边”，而“找一个城市断电”这个操作，本质就是“删除一个节点”。

理解到这一步，题目就从让人困惑的“地图题”变成了清晰的“树题”。我建议你在读题时养成一个习惯：看到节点数和边数的关系，先判断是不是树。如果是树，很多算法复杂度可以大幅降低，比如任意两点之间路径唯一，比如删除一个节点后，剩下的部分数量取决于这个节点的度数，这意味着一件事——你大概率只需要做一次 DFS 就能得到大部分答案。

1.2 删掉一个城市后，剩余区域是怎么拆出来的

当你从一棵树里删除一个节点 u，原来的树会散成若干个互不相连的连通块。这堆连通块怎么数？其实不是看 u 的度数减一，而是看 u 把整棵树切成了几份。

举个例子，如果 u 是叶子节点，那么删除它之后，剩下的树依然是一整个连通块；如果 u 的度数是 3，那么删除它之后，剩下通常会有 3 个连通块，分别挂在它的每个邻居身上，但有一个特殊情况：如果 u 不是我们任选的根节点，那么它的父节点方向也会被切出来一块，这个“上方块”的节点数等于总节点数减去 u 所在子树的大小。

题目要求的目标是：在所有可能被删除的城市里，找到那个让“最大的剩余连通块”尽可能小的城市编号。这和我们平时熟悉的“树的重心”定义完全一致：树的重心是让删除该点后最大连通块节点数最小的节点。所以这道题的模型一旦识别出来，你马上就能反应过来——它考的就是重心，而且不只是一个重心，还要求把所有满足条件的节点都按编号从小到大输出。

2. 核心算法：树的重心为什么是本题答案

2.1 一次DFS拿到所有节点的子树大小

要计算删除每个节点后会产生多大的最大连通块，最朴素的办法是枚举每个节点，然后分别模拟删掉它，对剩下的每个连通块做一次DFS统计节点数。这样做的时间复杂度是 O(N^2)，在 N 为 100000 级别的数据下肯定会超时。

正确做法是以任意一个节点为根，先对整个树做一次DFS，把每个节点的子树大小算出来。这里以节点 1 为根最省事，因为题目保证图连通，节点编号也从 1 开始。定义 size[u] 表示以 u 为根的子树里一共有多少个节点，递归计算时把每个子节点的 size 累加到父节点上，同时用一个 maxChild[u] 记录 u 的所有子节点中 size 最大的那一个。

为什么选任意根都可以？因为树的重心与根的选择无关。你可能会担心“如果根选得不一样，每个节点的子树方向就变了，计算出的重心还会一致吗？”答案是：重心的定义是客观的，你换一个根，只是把原来属于“父方向”的那块换了个名字，但它的大小依然会被总数减去当前子树大小表达出来，最终取最大值时结果保持不变。这也是这道题能放心以 1 为根去跑的前提。

2.2 每个节点的“最大连通块”等于什么

当某个节点 u 被删除，树会被拆成两部分来源：一部分是 u 的每个子节点所在的子树，这些子树的节点数分别是 size[v]；另一部分是“u 的父方向”，即整棵树中不落在 u 子树内的所有节点，它的节点数就是 N - size[u]。

所以在 DFS 完成后，删除 u 后形成的最大连通块大小，可以用一个公式直接算出来：

maxPart[u] = max(N - size[u], maxChild[u])

其中 maxChild[u] 是所有子节点 size[v] 的最大值。如果 u 是根节点，那么 N - size[u] = 0，也就是不存在父方向那块，公式依然成立。接着把每个节点都代入公式，记录最小的 maxPart 值，并收集所有达到这个最小值的节点编号，就是题目要求的结果。

这一步其实是整道题最简单的地方，前面的 DFS 已经帮你把所有信息准备好了，后面无非是 O(N) 扫一遍，甚至连第二次 DFS 都不需要。这也解释了为什么这题叫“找城市”而不叫“删城市”，因为出题人希望你把每个候选项的指标都算出来再去比较，而不是真的去模拟删除过程。

2.3 为什么答案可能有多个，以及输出顺序

树的重心在某些情况下不是唯一的。最典型的例子就是一条偶数节点的链，比如 1-2-3-4-5-6，删除节点 3 或者节点 4，剩余连通块的最大值都是 3；删除其他节点会得到更大的值，所以 3 和 4 都是重心。这是树的固有性质，不是题目故意挖坑。

如果你已经刷过一些树形DP题，应该知道一个结论：一棵树的重心最多只有两个，并且当存在两个重心时，它们一定相邻。这道题要求输出所有满足条件的城市编号，所以你不能在找到第一个最小答案后就 break，必须继续遍历，把所有 maxPart 等于最小值的节点收集起来，最后按编号升序输出。

在实际写代码时，建议先维护一个变量 minPart，初始值设为一个足够大的数或用 N 当初始值都可以；然后遍历 1 到 N，遇到更小的 maxPart 就清空答案数组重新收集，遇到相等的就把当前编号追加进去。这种写法比两遍遍历更干净，也不容易漏答案。

3. 四语言实战代码：Java、JS、Python、C

3.1 Java：邻接表加递归DFS，最直观的版本

Java 在这种树题里的标准实现是 ArrayList 数组做邻接表，递归计算子树大小。如果你的机试环境允许递归深度到十万，这个版本可以直接用；如果出现栈溢出，再考虑改成迭代写法，我在后面的踩坑部分会专门说。

import java.io.*; import java.util.*; public class Main { static int[] size; static int[] maxChild; static ArrayList<Integer>[] graph; static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line = br.readLine(); while (line != null && !line.trim().isEmpty()) { n = Integer.parseInt(line.trim()); size = new int[n + 1]; maxChild = new int[n + 1]; graph = new ArrayList[n + 1]; for (int i = 1; i <= n; i++) { graph[i] = new ArrayList<>(); } for (int i = 0; i < n - 1; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); graph[u].add(v); graph[v].add(u); } solve(); line = br.readLine(); } } static void solve() { dfs(1, 0); int minPart = Integer.MAX_VALUE; StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { int part = Math.max(n - size[i], maxChild[i]); if (part < minPart) { minPart = part; sb = new StringBuilder().append(i); } else if (part == minPart) { sb.append(' ').append(i); } } System.out.println(sb); } static void dfs(int u, int parent) { size[u] = 1; for (int v : graph[u]) { if (v == parent) continue; dfs(v, u); size[u] += size[v]; maxChild[u] = Math.max(maxChild[u], size[v]); } } }

这里有几个容易被忽略的细节。第一个是 graph 数组初始化必须从 1 到 n 都创建 ArrayList，不能偷懒只创建到 n，否则访问 graph[n] 会越界；第二个是 dfs 中要用 parent 参数判断回边，而不是用 visited 数组标记，因为树里没有环，用 parent 判断更省内存也更快；第三个是 maxChild[u] 的更新必须放在递归返回后，因为要拿到 size[v] 的最终值。

如果你在牛客、华为OD这类平台提交，Java 读入用 BufferedReader 是基本操作，Scanner 在数据量大时容易超时。这套代码在链状结构下递归深度可能达到十万，有些平台默认的 Java 栈不够用，我会在后面给出两个替代方案：一是启动参数加 -Xss10m，二是改成显式栈迭代。

3.2 JavaScript：用迭代DFS绕开递归深度限制

JavaScript 跑这道题时，最大的风险不是算法本身，而是 Node.js 的递归深度限制。默认情况下递归深度到了一万左右就会直接报 RangeError，而很多树的深度都在五位数，所以用递归写就是在冒险。稳妥的做法是用数组手动模拟栈，先做一个前序遍历记录节点顺序，再逆序遍历累加 size。

const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let lines = []; rl.on('line', (line) => { lines.push(line.trim()); }).on('close', () => { let idx = 0; while (idx < lines.length && lines[idx] !== '') { const n = parseInt(lines[idx++]); const graph = Array.from({ length: n + 1 }, () => []); for (let i = 0; i < n - 1; i++) { const [u, v] = lines[idx++].split(' ').map(Number); graph[u].push(v); graph[v].push(u); } solve(n, graph); } }); function solve(n, graph) { const size = new Array(n + 1).fill(1); const maxChild = new Array(n + 1).fill(0); 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 graph[u]) { if (v === parent[u]) continue; parent[v] = u; stack.push(v); } } for (let i = order.length - 1; i >= 0; i--) { const u = order[i]; const p = parent[u]; if (p > 0) { size[p] += size[u]; if (size[u] > maxChild[p]) { maxChild[p] = size[u]; } } } let minPart = Infinity; const ans = []; for (let i = 1; i <= n; i++) { const part = Math.max(n - size[i], maxChild[i]); if (part < minPart) { minPart = part; ans.length = 0; ans.push(i); } else if (part === minPart) { ans.push(i); } } console.log(ans.join(' ')); }

这里迭代DFS的原理其实很简单：先用栈做一次前序遍历，把访问顺序存进 order，同时记录每个节点的 parent；然后从 order 的尾部往前处理，此时处理到节点 u 时，它的所有子节点都已经把 size 累加到 u 上了，所以可以放心把 size[u] 累加到 parent[u]，并顺手更新 parent[u] 的 maxChild。

这种“先序记录、逆序统计”的写法比显式后序栈要容易理解得多，也不容易写错。唯一要注意的是初始 size 数组全部填 1，因为每个节点自己算一个；如果你忘记 fill(1)，整棵树的节点数就会越算越少。另一个容易踩的点是 parent 的初始值，根节点的 parent 设为 -1，这样逆序循环里用 p > 0 判断就不会把根节点错误累加。

3.3 Python：推荐迭代版，兼说递归写法

Python 选手写这道题，最稳的方案是 sys.stdin.buffer.read 一次性读入所有输入，搭配迭代DFS。Python 递归虽然可以 sys.setrecursionlimit(1000000) 强行提上限，但树很深时依然可能因为函数调用开销变慢，而且有些平台的递归栈管理会很微妙，所以我更推荐直接上迭代。

import sys def solve(n, edges): graph = [[] for _ in range(n + 1)] for u, v in edges: graph[u].append(v) graph[v].append(u) size = [1] * (n + 1) max_child = [0] * (n + 1) parent = [0] * (n + 1) order = [] stack = [1] parent[1] = -1 while stack: u = stack.pop() order.append(u) for v in graph[u]: if v == parent[u]: continue parent[v] = u stack.append(v) for u in reversed(order): p = parent[u] if p > 0: size[p] += size[u] if size[u] > max_child[p]: max_child[p] = size[u] min_part = n ans = [] for i in range(1, n + 1): part = max(n - size[i], max_child[i]) if part < min_part: min_part = part ans = [i] elif part == min_part: ans.append(i) print(' '.join(map(str, ans))) def main(): data = sys.stdin.buffer.read().split() if not data: return it = iter(data) try: while True: n = int(next(it)) edges = [] for _ in range(n - 1): u = int(next(it)) v = int(next(it)) edges.append((u, v)) solve(n, edges) except StopIteration: pass if __name__ == "__main__": main()

这套代码写出来比递归版长一点，但胜在不会遇到递归深度的天花板。程序中 reversed(order) 是关键，它保证每个节点的 size 在累加到父节点时已经是最终值。如果你只在纸上画一次链式数据跑一遍，就会直观地看到这个过程。

如果你更习惯递归写法，把 solve 里的遍历部分换成下面这样也行：

sys.setrecursionlimit(1 << 25) def dfs(u, parent): size[u] = 1 for v in graph[u]: if v == parent: continue dfs(v, u) size[u] += size[v] max_child[u] = max(max_child[u], size[v])

但要注意，这里 size、max_child、graph 都需要定义成外部变量或通过闭包访问，否则在递归函数里维护会很别扭。我的建议是，机试现场优先用迭代版，因为省去 setrecursionlimit 是否能成功的不确定性，一步到位。

3.4 C：数组模拟邻接表，快得干净利落

C 语言写这道题，最大的优势是内存可控、速度极快。很多人在 C 语言里习惯用指针或者二维数组存图，但其实最简单的是用三个一维数组模拟链式前向星：head 记录每个节点的第一条边下标，to 记录边的目标节点，nxt 记录同一起点的下一条边下标。这样既不用 malloc 一个二维数组，也不会因为 vector 的封装影响性能。

#include <stdio.h> #include <string.h> #define MAXN 100005 int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edgeCnt; int size[MAXN], maxChild[MAXN]; int ans[MAXN], ansCnt; void addEdge(int u, int v) { to[++edgeCnt] = v; nxt[edgeCnt] = head[u]; head[u] = edgeCnt; } void dfs(int u, int parent) { size[u] = 1; for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; if (v == parent) continue; dfs(v, u); size[u] += size[v]; if (size[v] > maxChild[u]) { maxChild[u] = size[v]; } } } int main() { int n; while (scanf("%d", &n) != EOF) { edgeCnt = 0; ansCnt = 0; memset(head, 0, sizeof(head)); memset(size, 0, sizeof(size)); memset(maxChild, 0, sizeof(maxChild)); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); addEdge(u, v); addEdge(v, u); } dfs(1, 0); int minPart = n; for (int i = 1; i <= n; i++) { int part = (n - size[i] > maxChild[i]) ? (n - size[i]) : maxChild[i]; if (part < minPart) { minPart = part; ansCnt = 0; ans[ansCnt++] = i; } else if (part == minPart) { ans[ansCnt++] = i; } } for (int i = 0; i < ansCnt; i++) { if (i) putchar(' '); printf("%d", ans[i]); } putchar('\n'); } return 0; }

这段代码有一个很值得注意的细节：addEdge 时 to[++edgeCnt] 的下标是从 1 开始的，所以 head 数组的初始值为 0 可以当作“没有下一条边”的哨兵。这个技巧在链式前向星里非常常见，比用 -1 初始化省了一个 memset 量。maxChild 数组在每次循环前都要清空，否则上一组测试数据残留会污染答案。

C 递归版在深度达到十万的链式数据下也有栈溢出风险，不过大部分 C 编译器的默认栈在 8MB 左右，递归调用里只压入两三个整型参数和返回地址，十万层通常能扛过去。如果平台比较严格，建议改成上一节 JavaScript 里那种“先序收集 + 逆序累加”的迭代写法，用数组模拟栈，逻辑完全一样。

4. 实战踩坑：从WA到AC的几个关键细节

4.1 递归深度和栈溢出是四语言都会遇到的坑

平时刷题时树的深度一般是几十、几百，递归很舒服；但机试数据里经常出现一条链，深度直接拉满到十万。Java 默认线程栈比较小，递归到一万层左右就可能抛 StackOverflowError；Node.js 则在更浅的位置就报 RangeError；Python 如果不手动调 setrecursionlimit 也会直接递归报错。

给 Java 用户的建议是，如果你们平台支持设置 JVM 参数，可以在提交配置里加 -Xss10m；如果不能设置，就把解题函数改成显式栈迭代。JS 用户没有这个选项，老老实实用我上面写的 order 数组方法。Python 用户如果在本地测试递归没问题，但提交时莫名其妙超时或崩溃，也建议直接切换到迭代版，别指望 setrecursionlimit 是银弹。

还有一个很有意思的现象：很多人写迭代栈时喜欢在邻接表里用 visited 数组，防止重复访问节点。在树上完全可以用 parent 数组替代 visited，因为每个节点访问子节点时只要不回到父节点就不会重复。这样不仅省内存，还天然避免了因为迭代顺序导致的父子关系混乱。

4.2 数组大小、下标偏移和清零问题

节点编号从 1 到 N，所以所有辅助数组都要开 n + 1 个，下标 0 闲置不用。如果你图省事只开了 n 个，访问 graph[n] 时会越界，C 语言里不会立刻报错，但会读到野数据，导致答案诡异。Java 里则会抛越界异常，直接在测试用例上崩掉。

多组输入时最隐蔽的问题就是忘记清零。C 语言里 memset 是最容易漏的，我自己的习惯是每次进入 while 循环的第一行就 memset 一遍，宁可多清也不能少清。Java 和 JS 因为每次都会 new 新数组，天然避免了上一组数据的残留；Python 里如果你把 graph、size 这些定义在 solve 函数内部，也不会有这个问题，所以尽量把整套逻辑封装进函数，而不是用全局限定。

链式前向星还有一个细节：to 数组和 nxt 数组要开到 2 倍边数，因为无向边要加两次。很多人第一次写这个结构会把 MAXN * 2 的 2 看成多余的，结果数组越界，而且 C 的越界检查很弱，可能会跑出完全错误的答案而不报错，非常难排查。

4.3 边界情况：N等于1、只有一个重心、链式结构

N = 1 的情况虽然简单，但最容易让你在测试用例上翻车。此时没有边，DFS 跑了根节点 1 之后就结束，size[1] = 1，maxChild[1] = 0，maxPart = max(0, 0) = 0。这意味着删除唯一的城市后剩余节点数为 0，答案就是 1。上面四份代码都能处理这种情况，但如果你手滑把 minPart 初始化为 0，就会找不到答案，所以初始值建议用 N 或更大的数。

链式结构是验证算法正确性的最好测试数据。比如 1-2-3-4-5-6，手算一遍：节点 3 的 N - size[3] = 6 - 4 = 2，maxChild[3] = 3，最大值为 3；节点 4 的 N - size[4] = 3，maxChild[4] = 2，最大值也是 3；其他节点都大于 3，所以答案输出 3 4。用这个小的链式数据去测试你写好的四段代码，可以快速发现是不是把 size 的方向弄反了。

另外可以自测一个星型图：中心节点 1 连接 2、3、4、5，其他节点互相不连。那么重心应该是中心 1，删除它之后最大连通块只有 1，其他叶子删除后最大连通块是 4。这个测试能帮你确认根节点方向是不是处理正确。

4.4 输入输出效率，机试里的隐形时间分

很多人算法本身没问题，但输入输出写得慢，导致超时。Java 用 Scanner，Python 用 input()，在 N 达到十万、边数接近十万时差距非常明显。Scanner 每次 nextInt 都有大量同步开销，Python 的 input() 每次读一行也要做字符串解码和换行处理，这些时间在严格限时的机试里很容易成为压死骆驼的最后一根稻草。

Java 应该用 BufferedReader + StringTokenizer；Python 用 sys.stdin.buffer.read().split() 一次性读进来；C 用 scanf 已经够快，但如果想更快可以用 getchar 手写读入函数；JS 用 readline 事件收集所有行也是一种默认做法。这些看起来不起眼的习惯，在数据量一大时能节省一半以上的 I/O 时间。

5. 这道题还能带出哪些经验

5.1 树的重心是一个高频模板，值得背下来

树的重心不只是机试考点，也是在很多树形问题里用来优化复杂度的工具，比如把一个长链问题通过重心分治来把递归深度降到 O(log N)。理解了“删除节点后最大连通块最小”的定义，你就同时理解了树上启发式合并里为什么常常要先求重心。

把这个模板用四门语言各写一遍，不是为了炫技，而是因为每一种语言都会暴露一类典型问题：Java 教你会不会用 BufferedReader 和泛型数组，JS 教你怎么躲开递归深度的坑，Python 教你在性能和写法之间做取舍，C 教你理解底层内存布局和链式前向星。同一个算法在不同语言里走一遍，比刷十道重复题有用得多。

5.2 换根DP的入门，从这道题搭桥

“找城市”本身只需要一次 DFS，但你可以顺手把它扩展成换根DP的入门题。如果题目改成“对每个城市，都输出删除它之后的最大连通块大小”，其实你现在已经会算了，因为你在遍历每个节点时计算出的 part 就是这个值。如果再改一个条件，比如城市的连接方式不再是一棵树，而是两条边会形成环，那就需要换根DP配合容斥思想去处理。

换根DP的核心是先固定一个根算出 size，然后通过父节点向子节点转移信息，比如计算“从任意节点出发到所有其他节点的距离和”，思路和这道题非常接近。建议你把今天这份找城市的代码保留下来，等刷到换根DP题目时回过来对照，会有一种“原来是同一种东西”的通透感。

5.3 并查集倒序加边，另一种值得知道的解法

除了重心模板，这道题还可以用并查集倒过来思考。假设把所有城市删光，然后按照某种顺序逐一把城市加回来，同时用并查集维护每个连通块的节点数。每加回一个节点，就和它周围已经存在的节点合并，记录当前最大连通块。倒序做完之后，每个节点加回的时机其实就对应正序里删除时的状态，也能找出最小最大连通块对应的城市。

这个思路的时间复杂度主要取决于并查集的合并轮数，整体接近 O(N α(N))，比两遍 DFS 更复杂，但在一些变种题里很常用。比如题目要求删除多个节点时，倒序加边往往比正序删除容易得多。所以即使你现在用 DFS 通过了这道题，也不妨在纸上推一遍并查集版本，加深对图论问题正反两种视角的理解。

最后再分享一个我个人做这类题的小习惯：拿到题目先不要急着写代码，拿一张纸画一棵 6 个节点的链和一个 5 个节点的星型，手动算出答案，再拿这个答案去验证代码。这一步每次能帮我排除掉一半以上的理解偏差，尤其是像“删除后剩余最大连通块”这种容易把父方向漏掉的场景，画一遍比看十遍题目都管用。