删去一条边分成两个连通块,使两块的结点数之差最小。
给定一棵 n 个结点的树。选择一条边并删去,树分成两个连通块,求两个连通块结点数之差的最小绝对值。
n − s,差值是 |n − 2s|。|n − 2s| 取最小即可。子树大小删除一条边绝对值最小自底向上累加
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;随后 n−1 行每条边的两个端点 |
| 输出 | 两个连通块结点数之差的最小绝对值 |
| 数据范围 | 2 ≤ n ≤ 2 × 10⁴ |
| 操作 | 删去恰好一条边 |
| 目标 | 最小化 |size₁ − size₂| |
sz[u] = 1 + Σ sz[儿子]|n − 2·sz[u]| 取最小以 1 为根,链条就是 1 → 2 → 3 → 4。
| 结点(子树) | 子树大小 s | 另一块大小 n−s | 差值 |n−2s| |
|---|---|---|---|
| 2 | 3 | 1 | 2 |
| 3 | 2 | 2 | 0 |
| 4 | 1 | 3 | 2 |
最小差值 0 ✓(删边 2−3,得到 {1,2} 与 {3,4})
sz[4] = 1(叶子)
sz[3] = 1 + sz[4] = 2
sz[2] = 1 + sz[3] = 3
sz[1] = 1 + sz[2] = 4(根,不用)
sz = [4, 3, 2, 1]
对结点 2:|4 − 2×3| = 2
对结点 3:|4 − 2×2| = 0 ← 最小
对结点 4:|4 − 2×1| = 2
所以答案是 0
✅ 0
结构:1 连着 2、3、4、5;5 连着 6。
| 结点(子树) | 子树包含 | 子树大小 s | 差值 |6−2s| |
|---|---|---|---|
| 2 | {2} | 1 | 4 |
| 3 | {3} | 1 | 4 |
| 4 | {4} | 1 | 4 |
| 6 | {6} | 1 | 4 |
| 5 | {5, 6} | 2 | 2 |
最小差值 2 ✓(删边 1−5,得到 {5,6} 与 {1,2,3,4})
sz[2] = sz[3] = sz[4] = sz[6] = 1
sz[5] = 1 + sz[6] = 2
sz[1] = 1 + 1 + 1 + 1 + 2 = 6 ✓(等于 n,正确)
根的子树大小必为 n(可作自检)
|6 − 2×1| = 4(四片叶子)
|6 − 2×2| = 2(结点 5)
最小 2
✅ 2
算完 sz 之后,检查一下 sz[1] 是否等于 n——如果不等,说明建图或遍历有问题(比如漏了结点、或者有环)。
这是一个非常好用的"结果自检"习惯。
u = 2..n(或所有非根结点)的子树。如果把根也算进去,会得到一个错误候选(差值为 n)。以 1 为根求所有子树大小,再对所有非根结点取 |n−2s| 最小
sz[父] += sz[子]。用迭代可以完全避免递归爆栈问题。删掉一条边,然后 DFS 数一遍两侧结点数
| 方案 | 复杂度(n = 2 × 10⁴) | 可行性 |
|---|---|---|
| 求子树大小 | 约 2 × 10⁴ | ✅ 瞬间 |
| 逐边暴力统计 | 约 4 × 10⁸ | ⚠️ 易超时 |
第一行输入 n,随后 n−1 行输入每条边的两个端点。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; vector<int> g[20005]; int fa[20005], sz[20005], order[20005]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } // 迭代 BFS 求顺序与父子关系 bool vis[20005] = {false}; int head = 0, tail = 0; order[tail++] = 1; vis[1] = true; while (head < tail) { int u = order[head++]; for (int v : g[u]) { if (!vis[v]) { vis[v] = true; fa[v] = u; order[tail++] = v; } } } for (int i = 1; i <= n; i++) sz[i] = 1; // 逆序累加:孩子的 sz 先确定,再加给父亲 for (int i = n - 1; i >= 1; i--) { int u = order[i]; sz[fa[u]] += sz[u]; } // 枚举每条"父—子边",求 |n − 2s| 的最小值 int ans = INT_MAX; for (int u = 2; u <= n; u++) { ans = min(ans, abs(n - 2 * sz[u])); } printf("%d\n", ans); return 0; }
sz[fa[u]] += sz[u] 时,sz[u] 已经是最终值了 ✓。这个技巧等价于"自底向上的后序",但完全避免了递归。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
| BFS 求 order 与 fa | 确定层次 | 父亲在儿子之前 |
sz[i] = 1 | 初始化 | 先算上自己 |
for (i = n−1; i >= 1; i--) | 逆序 | 保证儿子先加给父亲 |
sz[fa[u]] += sz[u] | 累加 | 子树大小汇总 |
u 从 2 到 n | 枚举边 | 跳过根(它没有父边) |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 0 | 题面样例 1(链,恰好平分) |
6 | 2 | 题面样例 2 |
2 | 0 | 两个结点,删唯一一条边恰好平分 |
3 | 1 | n 为奇数,最小差值为 1 |
5 | 1 | 5 个结点的链:切出 2 与 3,差 1 |
邻接表、父子关系、子树大小数组,均 O(n)。
✅ 约 2 万次操作,瞬间完成。核心是把"删边"转化为"枚举子树"。
// 求子树大小的通用模板(迭代版) BFS: order[], fa[] // 父亲先入队 for (i = 1..n) sz[i] = 1; for (i = n-1; i >= 1; i--) sz[fa[order[i]]] += sz[order[i]]; // 本题答案 int ans = INT_MAX; for (int u = 2; u <= n; u++) ans = min(ans, abs(n - 2 * sz[u])); // 由"子树大小"能解决的一类问题 // 1. 删一条边分成两块的平衡性(本题) // 2. 删一条边使某块大小恰好为 k // 3. 树的重心(使最大连通块最小的结点) // 4. 树上背包(子树的容量) // 树的重心求法(用到同样的 sz) // 对每个结点 u,删掉它后最大连通块大小 = // max(n - sz[u], max sz[v] (v 为 u 的儿子)) // 取这个值最小的结点即为重心
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 子树大小 | 自底向上累加 | 所有涉及"子树规模"的树题 |
| 逆序累加 | 用 BFS 顺序的逆序 | 避免递归且保证孩子先算 |
| 删边问题 | 转化为枚举子树 | 平衡性、切分类问题 |
|n − 2s| ≤ k 的边数即可。同一个 sz 数组能回答很多不同的问题——这也是"预处理一个通用信息"的价值。)