题解：P10723 [GESP202406 七级] 黑白翻转

WZWZWZWY · 2024-07-09 20:19:54 · 题解

第一眼：水题，感觉橙。

提交 WA 四次后，开始思考正解……

就不放错误思路了，以免误导大家。

正确思路：任意两个黑点之间的所有白点都不能被删除，所以只需要把两个黑点之间的所有白点都变成黑点就可以。

为什么这样是正确的？因为这是一颗树，若两个黑点之间有一个白点，那么删掉它肯定是不行的，否则图会不连通。

所以我们只要以一个黑点为根，向下，若能到另外一个黑点，这期间的所有白点都会变成黑点。

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

bool color[100005];
int ans, n;
vector <int> e[100005];

bool dfs(int x, int fa) {
    bool t = 0;
    for (int i = 0; i < e[x].size(); i++) {
        int to = e[x][i];
        if (to != fa && dfs(to, x)) t = 1; // 永远不要将该写 && 的地方写成 &，因为 && 会短路， & 不会 
    }
    if (!color[x] && t) ans++; // 白点的子树里有黑点，而根又是个黑点，所以白点被“两芝士夹一面包”了
    return (color[x] || t); // 返回这个点和这个点的子树是否有黑点
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> color[i];
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y); e[y].push_back(x);
    }
    int x = -1;
    for (int i = 1; i <= n; i++)
        if (color[i]) { // 找到黑色点 
            x = i; break;
        }
    dfs(x, 0);
    cout << ans;
}