企业官网建设流程全解析

如果你的机考题单里出现“找城市”这三个字，第一眼千万别被“城市”“道路”这两个词带跑。我第一次做这一类题目时，下意识就开始想最短路、多源 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] = 1，sz[5] = 1，sz[6] = 1
• sz[2] = 3，sz[3] = 2，sz[1] = 6

逐个节点算：

最小最大块为 3，对应的节点是 1 和 2。如果题目要求输出最小编号，答案就是 1；如果要求输出全部，就输出“1 2”。

3. Java与C的落地方案：邻接表存储与递归DFS

3.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 List<Integer>[] 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 四种实现横向对比

时间复杂度全部是 O(n)，空间复杂度全部是 O(n)。区别主要在于递归深度风险和代码风格的取舍。如果让我建议一个“一套代码打天下”的版本，那就是第 4 节的显式栈思路，它不依赖语言运行时对递归的宽容度，Java、C、Python、JS 都能平移过去。

5. 边界用例与实战经验：这些坑真的会考

5.1 边界用例：单节点、链状树、星形树

写代码之前，先想几个极端数据，能帮你避免低级错误。

第一个是 n = 1。此时没有任何边，删除唯一城市后，剩下的连通块大小是 0，最大块为 0，答案就是城市 1。上面的代码要不要特判？不需要。g[1] 为空列表，DFS 只访问节点 1，sz[1] = 1。第二次遍历时 maxPart = n - sz[1] = 0，best 初始是 n = 1，0 < 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]=1，sz[6]=2，sz[5]=3，sz[4]=4，sz[3]=5，sz[2]=6，sz[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 分基本就已经到手了。剩下的，就是把代码敲熟。