【图论 DFS】P10723 [GESP202406 七级] 黑白翻转|普及+

闻缺陷则喜何志丹

726人浏览 · 2026-09-04 07:00:00

闻缺陷则喜何志丹 · 2026-09-04 07:00:00 发布

本文涉及的基础知识点

C++图论
 C++DFS

[GESP202406 七级] 黑白翻转

题目描述

小杨有一棵包含 $n$ 个节点的树，这棵树上的任意一个节点要么是白色，要么是黑色。小杨认为一棵树是美丽树当且仅当在删除所有白色节点之后，剩余节点仍然组成一棵树。

小杨每次操作可以选择一个白色节点将它的颜色变为黑色，他想知道自己最少要执行多少次操作可以使得这棵树变为美丽树。

输入格式

第一行包含一个正整数 $n$ ，代表树的节点数。

第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ，其中如果 $a_i=0$ ，则节点 $i$ 的颜色为白色，否则为黑色。

之后 $n - 1$ 行，每行包含两个正整数 $x_i,y_i$ ，代表存在一条连接节点 $x_i$ 和 $y_i$ 的边。

输出格式

输出一个整数，代表最少执行的操作次数。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释

将节点 $1$ 和 $3$ 变为黑色即可使这棵树变为美丽树，此时删除白色节点 $5$ ，剩余黑色节点仍然组成一棵树。

数据范围

子任务编号	数据点占比	$n$	$a_i$	特殊条件
$1$	$30\%$	$\leq 10^5$	$0\leq a_i\leq 1$	树的形态为一条链
$2$	$30\%$	$\leq 10^5$	$0\leq a_i\leq 1$	只有两个节点颜色为黑色
$3$	$40\%$	$\leq 10^5$	$0\leq a_i\leq 1$

对于全部数据，保证有 $1\leq n\leq 10^5$ ， $0\leq a_i\leq 1$ 。

错误解法：图论树

转成以0为根的有根树。cnt[i]记录i子树，黑色节点的数量，如果cnt[i] >0且i是白色节点，ans++。
本解：
假定删除一个节点后，会分成多个子树，变色。
错误原因：
根子树可能为空，如：cur是0。
也可能根子树全部是变色，会被删除。

拓扑排序

白色叶子节点，才会删除。白色节点的数量-删除的叶子的数量就是答案。

代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	scanf("%d", &n);
	vector<T> ret(n);
	for(int i=0;i < n ;i++) {
		cin >> ret[i];
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

class CNeiBo
{
public:
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Two(int n, vector<pair<int,int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& [i1,i2] : edges)
		{
			vNeiBo[i1 - iBase].emplace_back(i2 - iBase);
			if (!bDirect)
			{
				vNeiBo[i2 - iBase].emplace_back(i1 - iBase);
			}
		}
		return vNeiBo;
	}
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};
class CTopSort
{
public:
	template <class T = vector<int> >
	void Init(const vector<T>& vNeiBo, bool bDirect)
	{
		const int iDelOutDeg = bDirect ? 0 : 1;
		m_c = vNeiBo.size();
		m_vBackNeiBo.resize(m_c);
		vector<int> vOutDeg(m_c);
		for (int cur = 0; cur < m_c; cur++)
		{
			vOutDeg[cur] = vNeiBo[cur].size();
			for (const auto& next : vNeiBo[cur])
			{
				m_vBackNeiBo[next].emplace_back(cur);
			}
		}
		vector<bool> m_vHasDo(m_c);
		queue<int> que;
		for (int i = 0; i < m_c; i++)
		{
			if (vOutDeg[i] <= iDelOutDeg)
			{
				m_vHasDo[i] = true;
				if (OnDo(i)) {
					que.emplace(i);
				}
			}
		}

		while (que.size())
		{
			const int cur = que.front();
			que.pop();
			for (const auto& next : m_vBackNeiBo[cur])
			{
				if (m_vHasDo[next])
				{
					continue;
				}
				vOutDeg[next]--;
				if (vOutDeg[next] <= iDelOutDeg)
				{
					m_vHasDo[next] = true;
					if (OnDo(next)) {
						que.emplace(next);
					}
				}
			}
		};
	}
	int m_c;
protected:
	virtual bool OnDo(int cur) = 0;
	vector<vector<int>> m_vBackNeiBo;
};

class CMyTTopSort :public CTopSort {
public:
	CMyTTopSort(const vector<int>& a) :m_a(a) {

	}
	virtual bool OnDo(int cur)
	{
		if (0 == m_a[cur]) { m_iDel++; return true; }
		return false;
	}
	const vector<int>& m_a;
	int m_iDel = 0;
};
//P10723 [GESP202406 七级] 黑白翻转
class Solution {
public:
	int Ans(const vector<int>& a, vector<pair<int, int>>& edge) {
		const int N = a.size();
		auto neiBo = CNeiBo::Two(N, edge, false, 1);
		CMyTTopSort top(a);
		top.Init(neiBo, false);
		const int c1 = count(a.begin(), a.end(), 0);
		return c1 - top.m_iDel;
	}
};


int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	int n;
	cin >> n ;
	auto a = Read<int>(n);
	auto edge = Read<pair<int, int>>(n - 1);
	auto res = Solution().Ans(a,edge);
#ifdef _DEBUG
	//printf("K=%d", K);
	//Out(a, ",a=");
	//Out(edge, ",edge=");
#endif // DEBUG	
	cout << res << endl;
	return 0;
}

单元测试

vector<int> a;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod11)
		{
			a = { 0,1,0,1,0 }, edge = { {1,2},{1,3},{3,4},{3,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			a = { 0,0,0,0,0 }, edge = { {1,2},{2,3},{3,4},{4,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod13)
		{
			a = { 1,1,1,1,0 }, edge = { {1,2},{2,3},{3,4},{4,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod14)
		{
			a = { 1,1,1,0,1 }, edge = { {1,2},{2,3},{3,4},{4,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod15)
		{
			a = { 1,1,1,0,1 }, edge = { {1,2},{1,3},{2,4},{3,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod16)
		{
			a = { 1,1,0,1,1 }, edge = { {1,2},{1,3},{2,4},{3,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod17)
		{
			a = { 1,1,1,0,0 }, edge = { {1,2},{1,3},{2,4},{3,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod18)
		{
			a = { 0,1,1,1,1 }, edge = { {1,2},{1,3},{2,4},{3,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod19)
		{
			a = { 0,0,0,1,1 }, edge = { {1,2},{1,3},{2,4},{3,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod20)
		{
			const int N = 9;
			a.resize(N);
			edge.resize(N - 1);
			for (int i = 0; i + 1 < N; i++) {
				edge[i]=make_pair(i + 1, i + 2);
			}
			for (int i = 0; i < (1<<N); i++) {
				for (int j = 0; j <N; j++) {
					a[j] = i && (1 << j);
				}
				auto res = Solution().Ans(a, edge);
				int res1 = count(a.begin(), a.end(), 0);
				int c1 = 0,c2=0;
				while ((c1 < N) && (a[c1] == 0)) {
					c1++;
				}
				while ((c2 <N) && (a[N - 1 - c2] == 0)) {
					c2++;
				}
				res1 = max(0, res1 - c1 - c2);
				AssertEx(res1, res);
			}
		}
		TEST_METHOD(TestMethod21)
		{
			a = { 0,1,1,1,1 }, edge = { {1,2},{2,3},{3,4},{4,5} };
			auto res = Solution().Ans(a, edge);
			AssertEx(0, res);
		}

扩展阅读

计算几何为骨，排样优化为魂
作品：亲士CAD工具箱
经典文章推荐：二维排样
万物皆数学
查阅鄙人的博文，请点击博文下载学院导航
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。