自动搬运

查看原文

来自洛谷，原作者为

	WZWZWZWY 一只蜷缩在只因房里敲代码的蒟蒻（真）|| ╯ω╰ || 这只蒟蒻已经被滚去学whk了qwq

搬运于2025-08-24 23:00:38，当前版本为作者最后更新于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;
}