GESP 题解库 / 6 级题解 / [GESP202609 六级] 分树规划 · 第 27 / 27 题
GESP202609 六级 · · 中等

分树规划

删去一条边分成两个连通块,使两块的结点数之差最小。

📊
n ≤ 2 × 10⁴
结点数量
🔢
int
差值范围
⚡
O(n)
时间复杂度
🎯
子树大小 + 绝对值最小
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定一棵 n 个结点的树。选择一条边并删去,树分成两个连通块,求两个连通块结点数之差的最小绝对值。

💡
人话翻译:删掉一条边后,其中一个连通块就是"被删边下方那棵子树"。
所以只要求出每条边下方子树的大小 s,另一块的大小就是 n − s,差值是 |n − 2s|。
把所有边的 |n − 2s| 取最小即可。
于是问题归结为"求所有子树的大小",一次 DFS/BFS 就能 O(n) 完成。

🔍 关键词提取

子树大小删除一条边绝对值最小自底向上累加

已知条件

项目说明
输入第一行 n;随后 n−1 行每条边的两个端点
输出两个连通块结点数之差的最小绝对值
数据范围2 ≤ n ≤ 2 × 10⁴
操作删去恰好一条边
目标最小化 |size₁ − size₂|

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 求子树大小 → 取 |n − 2s| 最小
🧠 关键转化
删边 = 切出一棵子树
两块大小为 s 与 n − s
差值 = |n − 2s|
于是只需枚举所有子树
📏 子树大小
以 1 为根
自底向上 sz[u] = 1 + Σ sz[儿子]
用后序或逆 BFS 序累加
O(n)
✅ 求答案
遍历每个非根结点 u
ans = min(ans, |n − 2·sz[u]|)
n 为偶数时可能取到 0
n 为奇数时最小为 1
⚠️ 易错点
递归 DFS 爆栈(n = 2×10⁴ 时链状也可能爆)
把根也统计进去(没意义)
忘记取绝对值
用 long long 没必要但无害
03
样例手算推导
两个样例的完整推演

🧮 样例 1:n = 4 的链 1−2−3−4,答案 0

以 1 为根,链条就是 1 → 2 → 3 → 4。

结点(子树)子树大小 s另一块大小 n−s差值 |n−2s|
2312
3220
4132

最小差值 0 ✓(删边 2−3,得到 {1,2} 与 {3,4})

1
先求子树大小

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
再算差值

对结点 2:|4 − 2×3| = 2

对结点 3:|4 − 2×2| = 0 ← 最小

对结点 4:|4 − 2×1| = 2

所以答案是 0

✅ 0

💡
n 为偶数时可以做到完全均分(前提是存在大小为 n/2 的子树)。
样例 1 中 n = 4,结点 3 的子树大小恰好是 2 = n/2,所以能完美平分 ✓。而 n 为奇数时,两块大小必然一奇一偶,差值最小只能是 1。

🧮 样例 2:n = 6,边为 (1,2)、(1,3)、(1,4)、(1,5)、(5,6),答案 2

结构:1 连着 2、3、4、5;5 连着 6。

结点(子树)子树包含子树大小 s差值 |6−2s|
2{2}14
3{3}14
4{4}14
6{6}14
5{5, 6}22

最小差值 2 ✓(删边 1−5,得到 {5,6} 与 {1,2,3,4})

1
长度计算

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(可作自检)

2
差值

|6 − 2×1| = 4(四片叶子)

|6 − 2×2| = 2(结点 5)

最小 2

✅ 2

💡 一个自检技巧

算完 sz 之后,检查一下 sz[1] 是否等于 n——如果不等,说明建图或遍历有问题(比如漏了结点、或者有环)。
这是一个非常好用的"结果自检"习惯。

⚠️
关于"根结点"的说明:根结点自身没有"父边",所以它不产生任何一条"可删除的边"。
因此遍历时要跳过根,只统计 u = 2..n(或所有非根结点)的子树。如果把根也算进去,会得到一个错误候选(差值为 n)。
04
解法对比
子树大小 O(n) vs 枚举边后暴力统计

⚔️ 解法对比

🟢 一次遍历求子树大小(推荐) 推荐

以 1 为根求所有子树大小,再对所有非根结点取 |n−2s| 最小

  • 时间 O(n)
  • n = 2 × 10⁴ 时约 2 × 10⁴
  • 代码 35 行(迭代版)
  • 空间 O(n)
💡
实现要点:先 BFS/DFS 得到遍历顺序,再逆序累加 sz[父] += sz[子]。用迭代可以完全避免递归爆栈问题。

🟠 枚举每条边后各自统计连通块

删掉一条边,然后 DFS 数一遍两侧结点数

  • 每条边 O(n)
  • 总计 O(n²) = 4 × 10⁸
  • 可能超时
  • 实现也更麻烦
⚠️
量级对比:O(n²) = 4 × 10⁸ vs O(n) = 2 × 10⁴——差了 2 万倍。而且"子树大小"这个信息对所有边都是共用的,算一次就够。

📈 性能对比

方案复杂度(n = 2 × 10⁴)可行性
求子树大小约 2 × 10⁴✅ 瞬间
逐边暴力统计约 4 × 10⁸⚠️ 易超时
05
算法流程图
迭代求子树大小后取最小差值
开始读入 n 和 n−1 条边;用邻接表建树从结点 1 出发做迭代 BFS,得到顺序 order 与父子关系 fa初始化 sz[i] = 1按 order 的逆序处理每个结点 u(从叶子往根)sz[fa[u]] = sz[fa[u]] + sz[u]对每个非根结点 u:ans = min(ans, |n − 2 × sz[u]|)输出 ans处理下一个结点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 最小结点数差

第一行输入 n,随后 n−1 行输入每条边的两个端点。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(迭代,避免爆栈)

#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;
}
🔑
为什么"逆序累加"是对的?BFS 得到的顺序满足:父亲一定排在儿子前面。所以逆序遍历时,一定会先处理完所有儿子,再处理父亲——
于是 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枚举边跳过根(它没有父边)
⚠️
四个坑:① 递归 DFS 导致爆栈(链状数据深度可达 2 × 10⁴);② 把根结点也算进答案(差值为 n,会误以为是候选);③ 忘记取绝对值;④ 忘记"逆序"累加(正序会把儿子的不完整值传给父亲)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
1 2 / 2 3 / 3 4
0题面样例 1(链,恰好平分)
6
1 2 / 1 3 / 1 4 / 1 5 / 5 6
2题面样例 2
2
1 2
0两个结点,删唯一一条边恰好平分
3
1 2 / 1 3
1n 为奇数,最小差值为 1
5
1 2 / 2 3 / 3 4 / 4 5
15 个结点的链:切出 2 与 3,差 1
✅
自查清单:① 用迭代吗?② 逆序累加吗?③ 跳过了根吗?

🚨 易错点清单

⚠️
递归爆栈:n = 2 × 10⁴ 的链会让递归深度过深,用 BFS + 逆序。
⚠️
把根也统计:根没有"上面的边",必须跳过。
⚠️
正序累加:必须先算儿子再算父亲,即逆序遍历。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
2 × 10⁴
运算量
约 2 × 10⁴

时间怎么算的?

空间都用在哪?

邻接表、父子关系、子树大小数组,均 O(n)。

✅ 约 2 万次操作,瞬间完成。核心是把"删边"转化为"枚举子树"。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 求子树大小的通用模板(迭代版)
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 顺序的逆序避免递归且保证孩子先算
删边问题转化为枚举子树平衡性、切分类问题
🌟
思考题:如果题目改成"删去一条边,要求两块的结点数之差不超过某个值 k,问有多少种删法",代码要怎么改?(提示:还是先求所有子树大小,然后统计满足 |n − 2s| ≤ k 的边数即可。同一个 sz 数组能回答很多不同的问题——这也是"预处理一个通用信息"的价值。)