GESP 题解库 / 7 级题解 / [GESP202406 七级] 黑白翻转 · 第 16 / 24 题
GESP202406 七级 · P10723 · 困难

黑白翻转

一棵黑白染色的树,最少把几个白点涂黑,才能让"删掉全部白点后剩下的黑点仍然连通"。

🌳
n ≤ 10⁵
树的大小
⚫
斯坦纳树内的白点数
答案本质
⚡
O(n)
时间复杂度
🎯
迭代 DFS + 方向计数
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨有一棵包含 n 个节点的树,树上每个节点要么是白色,要么是黑色(aᵢ = 0 表示白色,aᵢ = 1 表示黑色)。

小杨认为一棵树是美丽树,当且仅当删除所有白色节点之后,剩余节点仍然组成一棵树。

小杨每次操作可以选一个白色节点,把它的颜色变成黑色。求最少要执行多少次操作,才能使这棵树变为美丽树。

💡
人话翻译:把"删掉白点"理解成"只留下黑点"。
那么最终留下的黑点必须连成一片(连通)。你只能把白点涂黑,不能涂白、也不能删点,所以最后剩下的黑点集合 = 原来的黑点 + 你涂黑的那几个白点。
于是问题变成:找一个包含全部原有黑点的、点数最少的连通点集,答案是里面白点的个数。
这个"包含指定点集的最小连通子树"就是图论里的斯坦纳树。

🔍 关键词提取

树连通性斯坦纳树迭代 DFS方向计数

已知条件

项目说明
输入第一行 n;第二行 n 个 0/1 表示颜色;随后 n − 1 行边
输出一个整数:最少操作次数
数据范围1 ≤ n ≤ 10⁵,0 ≤ aᵢ ≤ 1
树的性质无向树:连通、无环,任意两点之间路径唯一
操作限制只能"白 → 黑",每个点至多变一次

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 原黑点的斯坦纳树 = 最终的黑点集合
🧠 结论先行
最终黑点集合必须连通且含全部原黑点
点数最小者 = 原黑点的斯坦纳树
答案 = 斯坦纳树里白点的个数
多涂一个都是浪费
📐 判定 v 在不在树里
定根 1,后序求出 cnt[v] = 子树内黑点数
数子节点中 cnt > 0 的个数 ch
看父侧:tot − cnt[v] 是否 > 0
ch + 父侧 ≥ 2 → 在斯坦纳树里
aᵥ = 1 → 也一定在里面
🧮 黑点很少的特殊情况
tot = 1:只有一个黑点,它自己就是一棵树 → 0
tot = 0:没有黑点 → 0
这两种情况公式都会自动给出 0
⚠️ 易错点
递归 DFS 在链上爆栈(必须迭代)
只数子侧、忘了"父侧"这一路方向
把"删白点"错读成"可以先删黑点"
邻接表数组开小(要开 n + 1)
03
样例手算推导
样例的手算推演

🧮 样例:n = 5,颜色 0 1 0 1 0,边 1-2, 1-3, 3-4, 3-5,答案 2

原黑点是 2 号和 4 号。它们之间唯一的路径是 2 → 1 → 3 → 4,所以斯坦纳树就是 {1, 2, 3, 4},里面的白点是 1 号和 3 号 —— 答案 2。

节点 vaᵥcnt[v] 子树内黑点数含黑点子节点数 ch父侧含黑点吗branch = ch + 父侧在斯坦纳树里吗
1022(2 号、3 号)tot − cnt = 0 → 无2✅ 在(要涂黑)
2110有(4 号在父侧)1✅ 在(本来就黑)
3011(4 号)有(2 号在父侧)2✅ 在(要涂黑)
4110有(2 号在父侧)1✅ 在(本来就黑)
5000有(2、4 号都在父侧)1❌ 不在,会被删掉

斯坦纳树 {1, 2, 3, 4} 里有 1、3 两个白点 → 答案 2 ✓

1
为什么 5 号点不算?

从 5 号出发只有一个方向:父节点 3 号那一侧

黑点 2 号和 4 号都挤在同一个方向里

说明 5 号不是"连接两个黑点"的必经之路

把它涂黑对连通性毫无帮助

❌ 不在斯坦纳树里

2
涂黑之后真的有美丽树吗?

把 1、3 涂黑后,黑点是 {1, 2, 3, 4}

删掉白点 5 号,剩下的边是 1-2、1-3、3-4

4 个点、3 条边、连通、无环

✅ 正好是一棵树

3
能不能只涂 1 个?

只涂 1 号:黑点 {1, 2, 4}

删掉白点 3、5 之后,1 和 4 之间没有边了

(原本靠 1-3-4 相连,3 被删掉了)

黑点分成 {1, 2} 和 {4} 两块,不连通

❌ 不连通,所以 2 次才是最少的

🔑
再解释一遍判定的来源:一个点只要两个方向上都有黑点,它就成了连接这些黑点的唯一通道(树上路径唯一,绕不过去),必须留下、必须变黑。
反过来,如果至多只有一个方向含黑点,那么从别的黑点走过来就"到头"了 —— 这里只是一条尾巴,涂黑它纯属浪费。

🧮 极端情况:黑点正好在一条链的两端

n = 5 的链 1-2-3-4-5,只有 1 号与 5 号是黑点。此时两个黑点之间的路径就是整条链,斯坦纳树 = 全部 5 个点。

节点 v两个方向都有黑点吗结论
2左有 1 号,右有 5 号✅ 涂黑
3左有 1 号,右有 5 号✅ 涂黑
4左有 1 号,右有 5 号✅ 涂黑
1
用公式核对 2 号点

定根 1 号:2 号的子节点是 3 号,cnt[3] = 1 > 0 → ch = 1

父侧:tot − cnt[2] = 2 − 1 = 1 > 0 → 父侧记 1

branch = 1 + 1 = 2 ≥ 2,且 a₂ = 0

✅ 计入答案(答案 = 3)

⚠️
链是最容易踩坑的形态:n = 10⁵ 的一条链上递归 DFS 会有 10⁵ 层,一定会栈溢出。
另外还要记住黑点少于 2 个时答案是 0:一个黑点自己就是一棵合法的树(tot = 1),一个黑点都没有时也不需要任何操作(tot = 0)。用公式跑这两种情况,答案会自然落到 0,不需要额外特判。
04
解法对比
正向"方向计数" vs 逆向"剪白叶"

⚔️ 解法对比

🟢 迭代 DFS + 方向计数(推荐) 推荐

定根后后序求出子树内黑点数 cnt,再按"方向数 ≥ 2"标记斯坦纳树

  • 时间 O(n),常数很小
  • 只需 par / cnt / order 三个数组
  • 代码约 35 行
  • 与"斯坦纳树"的定义一一对应,好解释
💡
为什么是"方向数 ≥ 2":把 v 的每条出边看成"一个方向",某个方向里含黑点,就说明那边有"客户"。
树上路径唯一,所以只要有两个不同方向含黑点,所有连接这些黑点的路径都必须穿过 v。
子侧用 cnt 数,父侧用 tot − cnt[v] 判断,两边加起来就是方向数。

🟠 逆向:反复剪掉"白叶子"

把度数为 1 的白点不停删掉,剩下的点就是斯坦纳树

  • 时间 O(n)
  • 用队列/栈做拓扑,代码约 30 行
  • 不需要定根,也不需要 cnt 数组
  • 需要维护度数,且要处理"只剩 1 个点"
⚠️
两种思路都对,但逆向做法有个坑:删到只剩一个点时如果它是白点,按"能删就删"会把它也删掉,所以必须写成"当且仅当剩余点数 > 1 且该白点度 ≤ 1 时才删"。
正向做法的判定条件更"干净",不容易写错。

📈 性能对比

方案复杂度代码量
迭代 DFS + 方向计数O(n),约 3 × 10⁵ 次约 35 行
逆向剪白叶(拓扑)O(n),需要维护度数约 30 行,边界更绕
递归 DFS 找路径O(n),但链上会爆栈❌ 运行错误
05
算法流程图
一次迭代 DFS + 一次方向计数扫描
开始读入 n、颜色 a、n − 1 条边,建邻接表从 1 号点出发做迭代 DFS,得到父节点 par 与"父先子后"的访问序 order倒序累加:cnt[v] = a[v] + Σ cnt[子节点],得子树内黑点数;tot = cnt[1]依次考察每个点 v:数出方向数 branch = (子节点中 cnt > 0 的个数)+(父侧是否含黑点)branch ≥ 2 吗?是 ✓该点属于斯坦纳树:若 a[v] = 0 则答案加 1否 ✗该点只是一条尾巴,跳过输出答案(最少操作次数)换下一个点 v 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 斯坦纳树最小涂黑数

第一行 n,第二行 n 个 0/1 颜色,随后 n − 1 行一条边。程序给出最少操作次数,并逐点展示"方向数"的判定过程,同时用暴力枚举(n ≤ 14)做对照。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码(迭代 DFS + 方向计数)

#include <bits/stdc++.h>
using namespace std;

int n;
int a[100005];          // 颜色:0 白,1 黑
int par[100005];        // 父节点,根的父节点记为 0
int cnt[100005];        // 子树内黑点个数
int order[100005];      // 迭代 DFS 的访问顺序(父一定排在子之前)
vector<int> g[100005];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    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);
    }

    // ---- 迭代 DFS:求父节点 + 访问顺序(避免链上递归爆栈)----
    vector<bool> vis(n + 1, false);
    vector<int> stk;
    stk.push_back(1);
    vis[1] = true;
    par[1] = 0;
    int top = 0;
    while (!stk.empty()) {
        int u = stk.back(); stk.pop_back();
        order[top++] = u;            // 出栈顺序保证:父一定先于子被记录
        for (int w : g[u]) {
            if (!vis[w]) {
                vis[w] = true;
                par[w] = u;
                stk.push_back(w);
            }
        }
    }

    // ---- 倒序累加:cnt[v] = a[v] + Σ cnt[子节点] ----
    for (int i = top - 1; i >= 0; i--) {
        int u = order[i];
        cnt[u] = a[u];
        for (int w : g[u]) if (par[w] == u) cnt[u] += cnt[w];
    }

    int tot = cnt[1];        // 全树黑点总数
    int ans = 0;

    // ---- 逐点判定:方向数 >= 2 的白点必须涂黑 ----
    for (int v = 1; v <= n; v++) {
        int ch = 0;                          // 子侧:含黑点的子节点个数
        for (int w : g[v]) if (par[w] == v && cnt[w] > 0) ch++;
        int up = (tot - cnt[v] > 0) ? 1 : 0; // 父侧是否含黑点
        if (a[v] == 0 && ch + up >= 2) ans++;
    }

    printf("%d\n", ans);
    return 0;
}
🔑
为什么队列/栈的"出栈顺序"里父节点一定排在子节点前面?因为我们是弹出 u 之后才把 u 的未访问邻居入栈,而 u 的子节点只可能在"u 被弹出之后"才第一次入栈,所以 u 一定先于它的所有子节点进入 order。
于是倒着遍历 order 时,每个点的子节点都已经算完了 —— 这就是"迭代版的后序遍历"。

📖 关键几行怎么看

代码作用为什么这样写
stk.push_back(w); vis[w] = true;迭代 DFS用显式栈代替递归,链长 10⁵ 也不会爆栈
for (int i = top - 1; i >= 0; i--)后序累加倒序保证子节点先于父节点算完
cnt[u] = a[u];初始化自己是不是黑点,先算进去(容易漏)
if (par[w] == u) cnt[u] += cnt[w];合并子树只加"真正的子节点",父节点不算
int up = (tot - cnt[v] > 0) ? 1 : 0;父侧判定父侧黑点数 = 总数 − 自己子树内的黑点数
ch + up >= 2斯坦纳判定至少两个方向有黑点 → 必经之路
⚠️
五个坑:① 用递归 DFS —— 链状数据直接爆栈(RE);② 忘记把父侧算进方向数,导致所有"拐点"都判错;③ cnt[u] 忘了先赋成 a[u];④ 把 >= 2 写成 >= 1(那样整棵树上的白点都会被涂黑);⑤ 把 a[v] == 0 漏掉,把本来就是黑点的位置也计进答案。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
5
0 1 0 1 0
1 2
1 3
3 4
3 5
2题面样例:斯坦纳树是 {1,2,3,4},白点 1、3 要涂黑
1
1
0n = 1 且本来就是黑点:单个点就是一棵树
2
1 1
1 2
0两个黑点之间就有边,已经连通
3
1 0 1
1 2
1 3
0黑点 1、3 之间有边直连,白点 2 是叶子,不用管它
6
1 0 0 1 0 0
1 2
1 3
3 4
3 5
5 6
1黑点 1、4 之间的路径是 1-3-4,只需涂黑 3 号
4
1 0 0 1
1 2
2 3
3 4
2链的两端是黑点:中间 2、3 两个白点都要涂
5
1 0 0 0 1
1 2
2 3
3 4
4 5
3黑点只在链的两端,中间三个白点全部要涂
✅
自查清单:① DFS 是迭代写的吗?② 方向数把父侧算进去了吗?③ 只统计白点吗?④ 用一个黑点的数据(答案应为 0)试过吗?

🚨 易错点清单

⚠️
递归 DFS 爆栈:树可能是一条 10⁵ 长的链,必须用显式栈做迭代 DFS。
⚠️
漏掉"父侧"方向:方向数 = 子节点中含黑点的个数 + 父侧是否含黑点,只数一边会把大量必经之路漏掉。
⚠️
cnt 初始化错:cnt[u] 必须先等于 a[u],再累加子节点。
⚠️
把已经黑的点也计进答案:只有 a[v] == 0 且方向数 ≥ 2 才需要操作。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
10⁵
总运算量
约 3 × 10⁵

时间怎么算的?

空间都用在哪?

邻接表 O(n + m) = O(n);另外还有 par、cnt、order 三个长度 n + 1 的 int 数组和一个 bool 数组。

✅ 线性扫描几毫秒就跑完。本题真正的门槛不在时间,而在两件事:把题意转化成"原黑点的斯坦纳树",以及把递归改成迭代以防爆栈。

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

🔗 常用技巧小抄

// ---- 树的迭代 DFS 模板:求父节点 + 父先子后的顺序 ----
vector<bool> vis(n + 1, false);
vector<int> stk{1};
vis[1] = true; par[1] = 0;
int top = 0;
while (!stk.empty()) {
    int u = stk.back(); stk.pop_back();
    order[top++] = u;                          // 出栈即记录
    for (int w : g[u])
        if (!vis[w]) { vis[w] = true; par[w] = u; stk.push_back(w); }
}
for (int i = top - 1; i >= 0; i--) {           // 倒序 = 后序遍历
    int u = order[i];
    // 此时所有子节点都已算完,可以安全地把子树信息合并到 u
}

// ---- "方向计数":判断一个点是不是必经之路 ----
// 子侧:统计有多少个子节点的子树里含"目标点"
// 父侧:tot - cnt[v] > 0 说明父节点那一侧也含目标点
// 两侧合计 >= 2  →  该点属于"目标点集的最小连通子树"
// 目标点本身一定属于这棵子树(它是"要连通的东西")

// ---- 等价的逆向写法:反复剪掉"白叶子" ----
// while (存在某个度为 1 的白点 且 剩余点数 > 1) 把它删掉;
// 剩下的点恰好就是斯坦纳树,答案 = 其中白点的个数

// ---- 推广:如果目标点不多(k <= 20)----
// 可以建"虚树",只保留目标点与它们的 LCA,规模降到 O(k)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
迭代 DFS避免 10⁵ 长的链把递归栈撑爆所有大规模树上遍历、网格遍历
子树计数 cnt一次后序累加求出"子树内黑点数"树形 DP、子树大小/权值和
方向计数 ≥ 2判定"必经之路",即最小连通子树虚树、斯坦纳树、关键点/割点
逆向剪叶把没用的尾巴一层层剥掉拓扑排序、树的直径、剥叶法
🌟
思考题:如果题目改成"每次可以选择一个黑点变白",要求"删掉白点后剩下的黑点仍然连通",最少要变白几个点?(提示:这时候黑点集合是固定的,你只能把黑点涂白来"精简"它,但涂白任何一个黑点都会破坏连通性——所以答案恒为 0,除非黑点本身就大于"斯坦纳树"。
换个角度想:本题的答案是"斯坦纳树里的白点数",而"斯坦纳树外的黑点数"恰好是另一个有意思的量,你能用同一套 cnt 数组把它也数出来吗?)