防爆栈非递归版本AC代码

如果标准解法代码在测试点 5 或 6（链状数据，深度 $10^5$）也出现“超时”或“卡死”，这通常不是因为计算太慢（时间复杂度确实是 $O(N)$），而是因为递归过深导致了栈溢出（Stack Overflow）。

在 Windows 环境下（或栈空间受限的 OJ），默认栈空间只有几 MB，无法支撑 $10^5$ 层深度的递归调用，程序会崩溃或挂起，表现得像超时。

为了解决这个问题，我们需要把递归 DFS 改写为 非递归（迭代） 的方式。

这里是完全防爆栈、防超时的非递归标准代码：

重构版标准代码 (非递归/迭代版)

核心原理：

1. BFS 确定层序：先用队列跑一遍 BFS，把节点按照从根到叶子的顺序存入数组 order，同时记录每个节点的父亲 parent。
2. 逆序更新：倒着遍历 order 数组（即从叶子往根走），这样处理每个节点时，其子树的信息一定已经计算完毕，完全模拟了递归的回溯过程。

/**
 * 题目：P10723 [GESP202406 七级] 黑白翻转
 * 版本：非递归优化版 (防爆栈)
 * 算法：BFS拓扑序 + 逆序遍历 (树形DP迭代写法)
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 */

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

int n;
int a[MAXN];            // 颜色
vector<int> adj[MAXN];  // 邻接表
int sz[MAXN];           // 子树黑点数
int parent[MAXN];       // 记录父节点
int total_black = 0;    // 总黑点数
int needed_edges = 0;   // 答案

void solve() {
    // 1. 高速 IO
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n)) return;

    // 清空数据 (如果有多组数据)
    for(int i=1; i<=n; i++) adj[i].clear();
    total_black = 0;
    needed_edges = 0;

    // 2. 读入颜色
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 1) total_black++;
    }

    // 3. 读入边
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 特判
    if (total_black == 0) {
        cout << 1 << "\n"; // 使用 \n 替代 endl
        return;
    }

    // ==========================================
    // 非递归核心逻辑
    // ==========================================
    
    // 步骤 1: BFS 建立树的拓扑序列 (确定父子关系)
    // order 存储访问顺序，parent 存储父节点
    vector<int> order; 
    order.reserve(n); // 预分配内存优化
    
    queue<int> q;
    vector<bool> visited(n + 1, false);

    // 假设 1 号点为根
    q.push(1);
    visited[1] = true;
    parent[1] = 0; // 根节点没有父亲

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                parent[v] = u; // 记录 v 的父亲是 u
                q.push(v);
            }
        }
    }

    // 步骤 2: 初始化 sz 数组
    // sz[i] 初始值为该节点本身的颜色贡献
    for(int i = 1; i <= n; i++) {
        sz[i] = a[i];
    }

    // 步骤 3: 逆序遍历 (从叶子向根回溯)
    // 类似于后序遍历
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        int p = parent[u];

        // 如果不是根节点，就需要向父亲汇报
        if (p != 0) {
            // 累加当前子树黑点数给父亲
            sz[p] += sz[u];

            // 判断连接 u 和 p 的这条边是否需要保留
            // u 是 p 的子节点。
            // 边 u-p 把树切两半：
            // 半边 1: u 的子树，黑点数 sz[u]
            // 半边 2: 剩余部分，黑点数 total_black - sz[u]
            if (sz[u] > 0 && sz[u] < total_black) {
                needed_edges++;
            }
        }
    }

    // 最终计算
    int nodes_in_subtree = needed_edges + 1;
    cout << nodes_in_subtree - total_black << "\n";
}

int main() {
    solve();
    return 0;
}

为什么这个代码不会超时/崩溃？

1. 内存管理：

   • 递归 DFS 使用的是栈内存（Stack）。栈空间很小（通常几MB），一旦递归层数过深（如 $10^5$），栈就会爆满，操作系统会强制终止程序，表现为“运行错误”或“无响应超时”。
   • 非递归 BFS 使用的是堆内存（Heap）（vector, queue 都在堆上）。堆空间非常大（通常有几百MB甚至GB），完全可以存下 $10^5$ 级别的数据。

2. 常数优化：

   • 消除了递归调用的函数开销。
   • 使用 reserve 预分配内存，减少 vector 扩容开销。
   • 使用 \n 代替 endl，大幅提升输出速度。

你可以用这个代码去跑刚刚生成器生成的 6.in，应该是秒出的。

这是一个功能完备的 C++ 数据生成器。它集成了标准题解逻辑（用于生成 .out）和针对题目不同子任务（链、双黑点、一般树）及边界情况（全白、单黑、全黑、星形图）的数据构造逻辑（用于生成 .in）。

数据生成策略

• 测试点 1: 极小数据 ($N=10$)，基础逻辑测试。
• 测试点 2: 全白 ($N=20$)，边界情况，答案应为 1。
• 测试点 3: 单黑 ($N=20$)，边界情况，答案应为 0。
• 测试点 4: 全黑 ($N=50$)，边界情况，答案应为 0。
• 测试点 5: 链状树 (Subtask 1, $N=1000$)，中等规模。
• 测试点 6: 链状树 (Subtask 1, $N=10^5$)，大规模，测试栈深度。
• 测试点 7: 双黑点 (Subtask 2, $N=10^5$)，测试两点间路径统计。
• 测试点 8: 星形图 ($N=10^5$)，中心为白，叶子部分黑，测试广度遍历。
• 测试点 9: 随机树 稀疏黑点 (Subtask 3, $N=10^5$)，约 10% 节点为黑。
• 测试点 10: 随机树 密集黑点 (Subtask 3, $N=10^5$)，约 50% 节点为黑。

C++ 数据生成器代码

/**
 * P10723 [GESP202406 七级] 黑白翻转 - 数据生成器 (高性能优化版)
 * 优化点：
 * 1. 解决了链状树导致的递归爆栈问题 (改为 BFS 拓扑序 + 逆序更新)
 * 2. 解决了 endl 导致的 I/O 缓慢问题 (改为 \n)
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
#include <random>
#include <ctime>
#include <queue> // 引入 queue 用于 BFS

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (非递归优化版)
// ==========================================
namespace Solution {
    const int MAXN = 100005;
    vector<int> adj[MAXN];
    int a[MAXN];
    int sz[MAXN];
    int parent[MAXN]; // 记录父节点，用于非递归更新
    int total_black;
    int needed_edges;

    // 优化：使用非递归方式计算
    // 思路：先跑一遍 BFS 得到拓扑序列（层序），然后反向遍历序列（从叶子到根）累加 sz
    void solve_non_recursive(int root, int n) {
        vector<int> order; // 存储 BFS 访问顺序
        queue<int> q;
        
        // 1. BFS 确定父子关系和遍历顺序
        q.push(root);
        parent[root] = 0;
        // 这里的 parent 数组兼具 visited 的功能(0表示无父或根)
        // 为了区分根节点的父0和未访问，初始化 parent 时要注意，或者使用额外 visited 数组
        // 这里简单处理：BFS生成树结构，记录 order
        
        vector<bool> visited(n + 1, false);
        visited[root] = true;
        
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);
            
            for(int v : adj[u]) {
                if(!visited[v]) {
                    visited[v] = true;
                    parent[v] = u; // 记录 v 的父亲是 u
                    q.push(v);
                }
            }
        }
        
        // 2. 初始化 sz
        for(int i = 1; i <= n; i++) sz[i] = a[i];
        
        // 3. 逆序遍历（相当于后序遍历：子 -> 父）
        // 从序列最后开始（最深的叶子），一直处理到根
        for(int i = n - 1; i >= 0; i--) {
            int u = order[i];
            int p = parent[u];
            
            if(p != 0) { // 如果不是根节点
                // 累加黑点数给父亲
                sz[p] += sz[u];
                
                // 判定连接 u 和 p 的这条边
                // u 是 p 的子节点，切断 u-p，u 这侧黑点数为 sz[u]
                if(sz[u] > 0 && sz[u] < total_black) {
                    needed_edges++;
                }
            }
        }
    }

    int solve(int n, const vector<int>& colors, const vector<pair<int, int>>& edges) {
        // 初始化全局变量
        for (int i = 1; i <= n; i++) adj[i].clear();
        total_black = 0;
        needed_edges = 0;

        // 载入数据
        for (int i = 1; i <= n; i++) {
            a[i] = colors[i - 1]; 
            if (a[i] == 1) total_black++;
        }

        for (const auto& e : edges) {
            adj[e.first].push_back(e.second);
            adj[e.second].push_back(e.first);
        }

        // 特判
        if (total_black == 0) return 1;
        if (total_black == 1) return 0;

        // 使用非递归求解
        solve_non_recursive(1, n);

        int nodes_needed = needed_edges + 1;
        return nodes_needed - total_black;
    }
}

// ==========================================
// Part 2: 数据构造工具
// ==========================================
mt19937 rng((unsigned)time(0));

int randInt(int min, int max) {
    return uniform_int_distribution<int>(min, max)(rng);
}

vector<pair<int, int>> generateTree(int n, int type) {
    vector<pair<int, int>> edges;
    if (type == 1) { // 链状
        for (int i = 1; i < n; i++) edges.push_back({i, i + 1});
    } else if (type == 2) { // 星形
        for (int i = 2; i <= n; i++) edges.push_back({1, i});
    } else { // 随机树
        for (int i = 2; i <= n; i++) {
            int p = randInt(1, i - 1);
            edges.push_back({p, i});
        }
    }
    return edges;
}

void shuffleLabels(int n, vector<int>& colors, vector<pair<int, int>>& edges) {
    vector<int> p(n + 1);
    iota(p.begin(), p.end(), 0);
    shuffle(p.begin() + 1, p.end(), rng);

    vector<int> new_colors(n);
    for (int i = 1; i <= n; i++) new_colors[p[i] - 1] = colors[i - 1];
    colors = new_colors;

    for (auto& e : edges) {
        e.first = p[e.first];
        e.second = p[e.second];
    }
}

// ==========================================
// Part 3: 测试点生成逻辑
// ==========================================
void makeData(int id) {
    string inName = to_string(id) + ".in";
    string outName = to_string(id) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    // 提升 cin/cout 效率 (虽然主要瓶颈在 endl)
    ios::sync_with_stdio(false);

    int N;
    vector<int> colors;
    vector<pair<int, int>> edges;

    // 参数配置
    if (id == 1) { N = 10; for (int i=0; i<N; i++) colors.push_back(randInt(0,1)); edges = generateTree(N, 0); }
    else if (id == 2) { N = 20; colors.assign(N, 0); edges = generateTree(N, 0); }
    else if (id == 3) { N = 20; colors.assign(N, 0); colors[randInt(0, N-1)] = 1; edges = generateTree(N, 0); }
    else if (id == 4) { N = 50; colors.assign(N, 1); edges = generateTree(N, 0); }
    else if (id == 5) { // 链状 1000
        N = 1000; 
        for (int i=0; i<N; i++) colors.push_back(randInt(0,1)); 
        edges = generateTree(N, 1); 
        shuffleLabels(N, colors, edges); 
    }
    else if (id == 6) { // 链状 100000 (原超时点)
        N = 100000; 
        for (int i=0; i<N; i++) colors.push_back(randInt(0,1)); 
        edges = generateTree(N, 1); 
        shuffleLabels(N, colors, edges); 
    }
    else if (id == 7) { 
        N = 100000; colors.assign(N, 0); 
        int u = randInt(0, N-1), v = randInt(0, N-1);
        while(u==v) v = randInt(0, N-1);
        colors[u]=1; colors[v]=1; 
        edges = generateTree(N, 0); 
    }
    else if (id == 8) { 
        N = 100000; colors.push_back(0); 
        for(int i=1; i<N; i++) colors.push_back(randInt(0,1)); 
        edges = generateTree(N, 2); 
        shuffleLabels(N, colors, edges); 
    }
    else if (id == 9) { 
        N = 100000; 
        for(int i=0; i<N; i++) colors.push_back(randInt(0, 10) < 1 ? 1 : 0); 
        edges = generateTree(N, 0); 
    }
    else { 
        N = 100000; 
        for(int i=0; i<N; i++) colors.push_back(randInt(0,1)); 
        edges = generateTree(N, 0); 
    }

    // ------------------------------------------
    // 写入文件 (优化 I/O)
    // ------------------------------------------
    fin << N << "\n"; // 使用 \n 而不是 endl
    for (int i = 0; i < N; i++) {
        fin << colors[i] << (i == N - 1 ? "" : " ");
    }
    fin << "\n";
    
    // 关键优化：这里的循环 10万次，必须用 \n，否则非常慢
    for (const auto& e : edges) {
        fin << e.first << " " << e.second << "\n"; 
    }

    fout << Solution::solve(N, colors, edges) << endl;

    fin.close();
    fout.close();
    cout << "Generated Case " << id << " (N=" << N << ")" << endl;
}

int main() {
    for (int i = 1; i <= 10; i++) {
        makeData(i);
    }
    cout << "All data generated successfully." << endl;
    return 0;
}

这是一个符合 NOIP C++14 竞赛标准的题解代码。

核心解题思路

1. 问题转化：
   • 题目要求“删除所有白色节点后，剩余（黑色）节点组成一棵树”。这意味着最终所有的黑色节点必须是连通的。
   • 我们的目标是用最少的操作（将白变黑），使得原本分散的黑色节点连在一起。
   • 这等价于在树上寻找包含所有初始黑色节点的最小连通子图（即树上的斯坦纳树 Steiner Tree）。
2. 连通子图的计算：
   • 如果我们要连接所有的黑色节点，哪些边是必须经过的？
   • 对于树上任意一条边 $(u, v)$，如果切断这条边，将树分成两部分。如果两部分都包含至少一个黑色节点，那么这条边就是连接这两部分黑色节点的必经之路，必须保留在最终的树中。
   • 如果是“死胡同”（即某一部分没有黑色节点），则这条边不需要保留。
3. 统计答案：
   • 我们统计出所有“必须保留的边”的数量，记为 $E_{needed}$。
   • 最小连通子图的点数 $V_{needed} = E_{needed} + 1$。
   • 需要执行的操作次数 = $V_{needed} - (\text{初始黑色节点数})$。
4. 特殊情况：
   • 如果初始没有黑色节点，根据树的定义（通常是非空），我们需要至少染黑 1 个点，操作数为 1。

标准代码 (C++14)

/**
 * 题目：P10723 [GESP202406 七级] 黑白翻转
 * 算法：DFS (树形结构遍历)、贡献法思维
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 */

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

// 最大节点数 10^5，稍微开大一点防止边界问题
const int MAXN = 100005;

int n;
int a[MAXN];           // 记录节点颜色：1为黑，0为白
vector<int> adj[MAXN]; // 邻接表存储树结构
int sz[MAXN];          // sz[u]：以 u 为根的子树中，初始黑色节点的数量
int total_black = 0;   // 整棵树中初始黑色节点的总数
int needed_edges = 0;  // 最小连通子图（虚树）所需的边数

/**
 * DFS 遍历树
 * 功能：
 * 1. 计算每个子树内的黑色节点数 sz[u]
 * 2. 判断每条边是否属于最小连通子图，并统计 needed_edges
 * 
 * @param u 当前节点
 * @param p 父节点（防止走回头路）
 */
void dfs(int u, int p) {
    // 初始化当前子树黑点数（如果自己是黑点则为1，否则为0）
    sz[u] = a[u];

    for (int v : adj[u]) {
        if (v == p) continue; // 只能向下搜索，不能回父节点

        dfs(v, u); // 递归处理子节点

        // 回溯阶段：累加子节点的黑点数到当前节点
        sz[u] += sz[v];

        // 关键点：边的判定逻辑
        // 对于边 u-v，它将树分为两部分：
        // 1. v 的子树 (含有 sz[v] 个黑点)
        // 2. 剩余部分 (含有 total_black - sz[v] 个黑点)
        // 如果两边都有黑点，说明这条边是沟通两侧黑点的必经之路，必须保留。
        if (sz[v] > 0 && sz[v] < total_black) {
            needed_edges++;
        }
    }
}

void solve() {
    // 读入节点数
    if (!(cin >> n)) return;

    total_black = 0;
    needed_edges = 0;

    // 读入颜色并统计总黑点数
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 1) total_black++;
    }

    // 读入边并建图
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 易错点：全白的情况
    // 如果没有黑点，树为空。为了构成一棵“树”，至少需要一个点。
    // 我们任选一个点染黑即可，操作数为 1。
    if (total_black == 0) {
        cout << 1 << endl;
        return;
    }

    // 从任意点（例如 1 号点）开始 DFS
    // 因为是统计边的属性，根节点的选择不影响结果
    dfs(1, 0);

    // 最小连通子图的点数 = 边数 + 1
    int nodes_in_subtree = needed_edges + 1;

    // 答案 = 最终需要的点数 - 已经有的黑点数
    int ans = nodes_in_subtree - total_black;

    cout << ans << endl;
}

int main() {
    // IO 优化：关闭同步流，加快 cin/cout 速度
    // 在 N=10^5 时非常有必要
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

复杂度分析与思考过程

1. 时间复杂度分析

• 分析：算法的核心是一次深度优先搜索（DFS）。
  • 在 DFS 过程中，每个节点被访问一次。
  • 每条边（无向边看作两条有向边）被遍历常数次（进入和返回）。
  • 所有操作（累加、判断）都是 $O(1)$ 的。
• 结论：时间复杂度为 $O(N)$。
• 适用性：题目给定的 $N \le 10^5$，线性复杂度可以在几十毫秒内完成，远低于 1秒 的时限，非常优秀。

2. 空间复杂度分析

• 分析：
  • 邻接表 adj 存储树结构，需要 $2(N-1)$ 个整数空间，即 $O(N)$。
  • 数组 a 和 sz 各需要 $N$ 个整数空间，即 $O(N)$。
  • 递归栈的深度最坏情况下（链状树）为 $N$，平均为 $\log N$。栈空间 $O(N)$。
• 结论：空间复杂度为 $O(N)$。
• 适用性：$10^5$ 个 int 约为 400KB，总内存占用在几 MB 级别，远低于 128MB/256MB 的限制。

3. 优化建议

当前算法在时间和空间上已经是理论最优解（因为读入数据就需要 $O(N)$），无需进一步优化。唯一需要注意的是 递归爆栈 风险：

• 在 Windows 环境下，默认栈空间较小，如果 $N=10^5$ 且树退化成一条链，DFS 可能会爆栈。
• 竞赛建议：NOI 系列比赛（Linux 环境）栈空间通常很大（与内存限制一致），直接写 DFS 没问题。如果担心栈溢出，可以改为手动模拟栈的 BFS 写法（即拓扑排序思想，从叶子节点向上剥离），但代码复杂度会增加，本题通常不需要。

你好！我是你的OI教练。很高兴能带你攻克这道 GESP 七级的图论题目《黑白翻转》。

这道题其实是图论中一个非常经典的模型：树上斯坦纳树（Steiner Tree）或者叫虚树的点数统计。别被这些名词吓到，它的核心逻辑其实就是“连连看”。

我们拿出草稿纸，把题目“剥皮抽筋”，看看它的本质是什么。

1. 读题关键词：你的“雷达”响了吗？

在读题时，请圈出以下决定解题策略的关键信息：

1. “美丽树...删除所有白色节点之后，剩余节点仍然组成一棵树”：
   • 翻译：所有黑色的节点必须连通。
   • 隐含条件：因为原图是树（无环），所以只要剩下的黑色节点是连通的，它们自然构成一棵子树。
   • 潜台词：你需要把分散在树上各个角落的黑色节点，用最少的白色节点把它们“串”起来。
2. “最少执行多少次操作”：
   • 我们只能把白色变成黑色（不能反向）。
   • 为了连通，我们必须填补黑色节点之间的路径。
   • 最少意味着：我们要找的是包含所有初始黑色节点的最小连通子图。

2. 预备知识点

要解决这道题，你需要掌握：

• 图的存储：邻接表 (vector<int> adj[])。
• DFS（深度优先搜索）：用于遍历树，计算子树信息。
• 贡献法思维：与其去模拟“把谁变黑”，不如统计“哪些边必须被保留”。

3. 启发式教学：草稿纸上的推演

假设树上有几个散落的黑点（比如下图中的 B1, B2, B3）。

       (Root)
         |
    W1 -- W2 -- B1
          |
    W3 -- W4 -- B2
          |
          B3

思考过程：

1. 为了让 B1, B2, B3 连通，中间的白色节点 W2, W4 必须变成黑色。W1, W3 不需要变。
2. 最终形成的黑色区域，其实就是涵盖所有初始黑点的最小子树。
3. 如何快速计算这个子树的大小？
   • 直接找点很难（需要求 LCA）。
   • 转换思路：我们要计算这个子树里有多少条边。
   • 点数 = 边数 + 1。

边的判定（核心魔法）： 随便拿一条边（比如切断它），这条边把树分成了两半。

• 如果两半都有黑点，说明这条边是“必经之路”，必须保留。
• 如果某一侧没有黑点，说明那一侧是“死胡同”，这条边不需要保留。

数学公式化： 我们随便选个根（比如节点 1），跑一遍 DFS。 对于每一条边 $u \to v$（$v$ 是 $u$ 的儿子）：

• 计算 $v$ 的子树里有多少个黑点，记为 sz[v]。
• 设总黑点数为 total。
• 这条边把树分为两部分：
  1. $v$ 的子树，黑点数为 sz[v]。
  2. 剩下的部分，黑点数为 total - sz[v]。
• 判定条件：如果 sz[v] > 0 且 total - sz[v] > 0（也就是 sz[v] < total），那么这条边必须在最小连通子图里。

最终计算：

• 统计所有满足条件的边数 edge_cnt。
• 最终黑点总数 = edge_cnt + 1。
• 需要翻转的次数 = 最终黑点总数 - 初始黑点总数。

特判： 如果 total == 0（一开始全是白的），由于树不能为空（通常定义），我们需要选 1 个点变黑，花费 1 次操作。

4. 标准代码 (NOIP C++14)

这个版本可以AC

/**
 * 题目：P10723 [GESP202406 七级] 黑白翻转
 * 考点：树形结构、DFS、连通性、贡献法
 * 时间复杂度：O(N)
 */

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MAXN = 100005;

int n;
int a[MAXN];          // 记录节点颜色，1为黑，0为白
vector<int> adj[MAXN]; // 邻接表存树
int sz[MAXN];         // sz[u] 表示以 u 为根的子树中黑色节点的数量
int total_black = 0;  // 初始黑色节点总数
int required_edges = 0; // 最小连通子图需要的边数

// DFS 遍历树，计算子树黑点数并统计有效边
// u: 当前节点, p: 父节点
void dfs(int u, int p) {
    sz[u] = a[u]; // 初始化：如果自己是黑点，贡献为1

    for (int v : adj[u]) {
        if (v == p) continue; // 防止走回头路

        dfs(v, u); // 递归处理子节点

        sz[u] += sz[v]; // 累加子树的黑点数

        // 核心判断逻辑：
        // 边 u-v 是否属于最小连通子图？
        // 条件：切断这条边，v的子树里有黑点，且整棵树除去v的子树外也有黑点
        if (sz[v] > 0 && sz[v] < total_black) {
            required_edges++;
        }
    }
}

void solve() {
    cin >> n;
    
    total_black = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 1) total_black++;
    }

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 特判：如果一开始没有黑点，根据题意"美丽树"需要是非空的树
    // 我们至少需要染黑 1 个点。
    if (total_black == 0) {
        cout << 1 << endl;
        return;
    }

    // 从 1 号点开始 DFS（假设 1 为根）
    dfs(1, 0);

    // 最小连通子图的点数 = 边数 + 1
    int final_nodes = required_edges + 1;

    // 答案 = 最终需要的黑点数 - 初始已有的黑点数
    cout << final_nodes - total_black << endl;
}

int main() {
    // IO 优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

5. 易错点与关键点注释

1. Total=0 的陷阱：
   • 如果整棵树一开始全是白的，根据逻辑公式，sz[v] > 0 永远不成立，算出来的边数是 0，计算结果会变成 $0+1-0=1$。
   • 但逻辑上，如果按照公式严谨推导，total=0 时 required_edges=0。
   • 这里特判输出 1 是为了保证逻辑清晰：没有黑点就造一个黑点。
2. Total=1 的情况：
   • 如果只有一个黑点，sz[v] < total (即 sz[v] < 1)，这就要求 sz[v] == 0。
   • 但前面的条件是 sz[v] > 0。
   • 所以没有边满足条件，required_edges = 0。
   • 答案：$0 + 1 - 1 = 0$。符合直觉（不需要操作）。
3. 根节点的选择：
   • 因为计算的是“边是否分割了黑点”，这属于无根树的拓扑属性，选谁做根 DFS 结果都一样。习惯上选 1。

学会这个“边的判定法”，以后遇到树上求包含某些关键点的最小连通块大小（虚树大小）的问题，就可以秒杀了！加油！