一棵黑白染色的树,最少把几个白点涂黑,才能让"删掉全部白点后剩下的黑点仍然连通"。
小杨有一棵包含 n 个节点的树,树上每个节点要么是白色,要么是黑色(aᵢ = 0 表示白色,aᵢ = 1 表示黑色)。
小杨认为一棵树是美丽树,当且仅当删除所有白色节点之后,剩余节点仍然组成一棵树。
小杨每次操作可以选一个白色节点,把它的颜色变成黑色。求最少要执行多少次操作,才能使这棵树变为美丽树。
树连通性斯坦纳树迭代 DFS方向计数
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个 0/1 表示颜色;随后 n − 1 行边 |
| 输出 | 一个整数:最少操作次数 |
| 数据范围 | 1 ≤ n ≤ 10⁵,0 ≤ aᵢ ≤ 1 |
| 树的性质 | 无向树:连通、无环,任意两点之间路径唯一 |
| 操作限制 | 只能"白 → 黑",每个点至多变一次 |
原黑点是 2 号和 4 号。它们之间唯一的路径是 2 → 1 → 3 → 4,所以斯坦纳树就是 {1, 2, 3, 4},里面的白点是 1 号和 3 号 —— 答案 2。
| 节点 v | aᵥ | cnt[v] 子树内黑点数 | 含黑点子节点数 ch | 父侧含黑点吗 | branch = ch + 父侧 | 在斯坦纳树里吗 |
|---|---|---|---|---|---|---|
| 1 | 0 | 2 | 2(2 号、3 号) | tot − cnt = 0 → 无 | 2 | ✅ 在(要涂黑) |
| 2 | 1 | 1 | 0 | 有(4 号在父侧) | 1 | ✅ 在(本来就黑) |
| 3 | 0 | 1 | 1(4 号) | 有(2 号在父侧) | 2 | ✅ 在(要涂黑) |
| 4 | 1 | 1 | 0 | 有(2 号在父侧) | 1 | ✅ 在(本来就黑) |
| 5 | 0 | 0 | 0 | 有(2、4 号都在父侧) | 1 | ❌ 不在,会被删掉 |
斯坦纳树 {1, 2, 3, 4} 里有 1、3 两个白点 → 答案 2 ✓
从 5 号出发只有一个方向:父节点 3 号那一侧
黑点 2 号和 4 号都挤在同一个方向里
说明 5 号不是"连接两个黑点"的必经之路
把它涂黑对连通性毫无帮助
❌ 不在斯坦纳树里
把 1、3 涂黑后,黑点是 {1, 2, 3, 4}
删掉白点 5 号,剩下的边是 1-2、1-3、3-4
4 个点、3 条边、连通、无环
✅ 正好是一棵树
只涂 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 号的子节点是 3 号,cnt[3] = 1 > 0 → ch = 1
父侧:tot − cnt[2] = 2 − 1 = 1 > 0 → 父侧记 1
branch = 1 + 1 = 2 ≥ 2,且 a₂ = 0
✅ 计入答案(答案 = 3)
定根后后序求出子树内黑点数 cnt,再按"方向数 ≥ 2"标记斯坦纳树
把度数为 1 的白点不停删掉,剩下的点就是斯坦纳树
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 迭代 DFS + 方向计数 | O(n),约 3 × 10⁵ 次 | 约 35 行 |
| 逆向剪白叶(拓扑) | O(n),需要维护度数 | 约 30 行,边界更绕 |
| 递归 DFS 找路径 | O(n),但链上会爆栈 | ❌ 运行错误 |
第一行 n,第二行 n 个 0/1 颜色,随后 n − 1 行一条边。程序给出最少操作次数,并逐点展示"方向数"的判定过程,同时用暴力枚举(n ≤ 14)做对照。
点按钮开始 →
#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; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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 | 斯坦纳判定 | 至少两个方向有黑点 → 必经之路 |
cnt[u] 忘了先赋成 a[u];④ 把 >= 2 写成 >= 1(那样整棵树上的白点都会被涂黑);⑤ 把 a[v] == 0 漏掉,把本来就是黑点的位置也计进答案。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 2 | 题面样例:斯坦纳树是 {1,2,3,4},白点 1、3 要涂黑 |
1 | 0 | n = 1 且本来就是黑点:单个点就是一棵树 |
2 | 0 | 两个黑点之间就有边,已经连通 |
3 | 0 | 黑点 1、3 之间有边直连,白点 2 是叶子,不用管它 |
6 | 1 | 黑点 1、4 之间的路径是 1-3-4,只需涂黑 3 号 |
4 | 2 | 链的两端是黑点:中间 2、3 两个白点都要涂 |
5 | 3 | 黑点只在链的两端,中间三个白点全部要涂 |
cnt[u] 必须先等于 a[u],再累加子节点。a[v] == 0 且方向数 ≥ 2 才需要操作。邻接表 O(n + m) = O(n);另外还有 par、cnt、order 三个长度 n + 1 的 int 数组和一个 bool 数组。
✅ 线性扫描几毫秒就跑完。本题真正的门槛不在时间,而在两件事:把题意转化成"原黑点的斯坦纳树",以及把递归改成迭代以防爆栈。
// ---- 树的迭代 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 | 判定"必经之路",即最小连通子树 | 虚树、斯坦纳树、关键点/割点 |
| 逆向剪叶 | 把没用的尾巴一层层剥掉 | 拓扑排序、树的直径、剥叶法 |