甘南藏族自治州网站建设_网站建设公司_UI设计师_seo优化

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[P10723 GESP202406 七级] 黑白翻转 - 洛谷

【题目描述】

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

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

【输入】

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

第二行包含n nn个非负整数a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1​,a2​,…,an​，其中如果a i = 0 a_i=0ai​=0，则节点i ii的颜色为白色，否则为黑色。

之后n − 1 n-1n−1行，每行包含两个正整数x i , y i x_i,y_ixi​,yi​，代表存在一条连接节点x i x_ixi​和y i y_iyi​的边。

【输出】

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

【输入样例】

5 0 1 0 1 0 1 2 1 3 3 4 3 5

【输出样例】

2

【算法标签】

《洛谷 P10723 黑白翻转》 #树形DP# #拓扑排序# #树的遍历# #GESP# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005,M=N*2;// M是边数的两倍，因为是无向图intn,ans;// n: 节点数, ans: 答案inta[N];// a[i]: 节点i的状态，0表示白色，1表示黑色inth[N],e[M],ne[M],idx;// 邻接表存储树结构// 添加无向边voidadd(inta,intb){e[idx]=b;// 存储边的终点ne[idx]=h[a];// 将新边插入链表头部h[a]=idx;// 更新头指针idx++;// 边编号自增}// 深度优先搜索// u: 当前节点// fa: 父节点，防止走回头路voiddfs(intu,intfa){ints=0;// 统计子节点中黑色节点的数量// 遍历当前节点的所有邻居for(inti=h[u];i!=-1;i=ne[i]){intj=e[i];// 邻居节点if(j==fa)// 如果是父节点，跳过{continue;}// 递归处理子树dfs(j,u);// 累加子节点的颜色s+=a[j];}// 关键条件判断：// 1. s > 0: 当前节点至少有一个黑色子节点// 2. a[u] == 0: 当前节点是白色if(s&&!a[u]){ans++;// 答案加1a[u]=1;// 将当前节点染成黑色}}intmain(){// 输入节点数cin>>n;// 初始化邻接表memset(h,-1,sizeof(h));// 输入每个节点的初始颜色for(inti=1;i<=n;i++){cin>>a[i];}// 输入n-1条边，构建树for(inti=1;i<n;i++){intu,v;cin>>u>>v;add(u,v);// 添加无向边add(v,u);}// 从任意一个黑色节点开始DFSfor(inti=1;i<=n;i++){if(a[i]==1)// 找到第一个黑色节点{dfs(i,0);// 从该节点开始DFS，父节点为0break;}}// 输出答案cout<<ans<<endl;return0;}

【运行结果】

5 0 1 0 1 0 1 2 1 3 3 4 3 5 2