G7005 [GESP202406 七级] 黑白翻转 题解

知识点：树、拓扑剥叶、贪心。

解题思路

反复删除白色叶节点，保留所有黑点之间的最小连通子树；答案是剩余白节点数。若原来没有黑点，则只需染一个节点。

为什么正确

任意两个黑点之间的唯一路径都必须全黑，路径之外的白枝可以舍去；剥叶恰留下这些必需路径。

易错点

全白树不能以空集合当作美丽树，答案为1；删除后新形成的白叶也需继续处理。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1);
    int black=0;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        black+=a[i];
    }
    vector<vector<int>>g(n+1);
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(!black) {
        cout<<1;
        return 0;
    }
    vector<int>deg(n+1),dead(n+1);
    queue<int>q;
    for(int i=1;i<=n;i++) {
        deg[i]=g[i].size();
        if(deg[i]<=1&&!a[i])q.push(i);
    }
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        if(dead[u])continue;
        dead[u]=1;
        for(int v:g[u])if(!dead[v]&&--deg[v]<=1&&!a[v])q.push(v);
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans+=!dead[i]&&!a[i];
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。