: 黑白翻转)
2024年6月GESP真题及题解(C++七级): 黑白翻转
题目描述
小杨有一棵包含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的边。
输出格式
输出一个整数，代表最少执行的操作次数。
输入输出样例 1
输入 1
5 0 1 0 1 0 1 2 1 3 3 4 3 5输出 1
2说明/提示
样例解释
将节点1 11和3 33变为黑色即可使这棵树变为美丽树，此时删除白色节点5 55，剩余黑色节点仍然组成一棵树。
数据范围
| 子任务编号 | 数据点占比 | n nn | a i a_iai | 特殊条件 |
|---|---|---|---|---|
| 1 11 | 30 % 30\%30% | ≤ 10 5 \leq 10^5≤105 | 0 ≤ a i ≤ 1 0\leq a_i\leq 10≤ai≤1 | 树的形态为一条链 |
| 2 22 | 30 % 30\%30% | ≤ 10 5 \leq 10^5≤105 | 0 ≤ a i ≤ 1 0\leq a_i\leq 10≤ai≤1 | 只有两个节点颜色为黑色 |
| 3 33 | 40 % 40\%40% | ≤ 10 5 \leq 10^5≤105 | 0 ≤ a i ≤ 1 0\leq a_i\leq 10≤ai≤1 |
对于全部数据，保证有1 ≤ n ≤ 10 5 1\leq n\leq 10^51≤n≤105，0 ≤ a i ≤ 1 0\leq a_i\leq 10≤ai≤1。
思路分析
算法思路
- 问题转化：美丽树要求删除所有白色节点后，剩余黑色节点仍构成一棵树，即所有黑色节点必须连通。通过将白色节点变为黑色来连接黑色节点，需要找到最少的白色节点数，使得所有黑色节点连通。
- 核心观察：从任意一个黑色节点（如第一个黑色节点）作为根进行DFS，计算每个节点的子树中黑色节点的数量。若一个节点的子树中包含黑色节点，则该节点必须保留（如果是白色则需要变为黑色），否则删除该节点不会影响黑色节点的连通性。
- 计算最少操作：统计所有子树中包含黑色节点的节点数，减去初始黑色节点数，即为需要将白色变为黑色的节点数（最少操作次数）。
代码流程
- 初始化：读入节点颜色，记录黑色节点数并选择第一个黑色节点作为根。
- 建图：读入边，构建无向树。
- DFS计算：从根节点开始DFS，后序遍历累加子树中黑色节点数到父节点，使
vis[i]最终表示以i为根的子树中黑色节点的总数。 - 统计结果：遍历所有节点，若
vis[i] > 0则说明该节点的子树中有黑色节点，计数一次。最终ans为所有此类节点数，减去初始黑色节点数num1，得到需要操作的白色节点数。
时间复杂度
- DFS遍历所有节点和边，时间复杂度为O(n)。
- 空间复杂度为O(n)，用于存储树和图。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintN=200010;// 定义最大节点数，开两倍以防无向边存储intn,a,b,ans,num,root;// n:节点数，a,b:临时边变量，ans:统计结果，num1:黑色节点数量，root:选定的根节点（第一个黑色节点）intvis[N];// vis[i]：初始表示节点i的颜色（黑色为1，白色为0），DFS后表示以i为根的子树中黑色节点的总数vector<int>e[N];// 邻接表存储树的边// 深度优先搜索，计算每个节点的子树中黑色节点数量// u: 当前节点，f: 父节点voiddfs(intu,intf){// 遍历当前节点的所有邻居for(intv:e[u]){if(v==f)continue;// 跳过父节点，避免回环dfs(v,u);// 递归处理子节点vis[u]+=vis[v];// 将子节点的黑色节点数累加到当前节点}return;}intmain(){// 读入节点数scanf("%d",&n);intc;// 读入每个节点的颜色，并初始化vis数组for(inti=1;i<=n;i++){scanf("%d",&c);if(c==1){// 如果节点是黑色vis[i]=1;// 标记该节点为黑色（计数1）num++;// 黑色节点计数加一if(num==1)root=i;// 记录第一个黑色节点作为根节点}// 白色节点vis[i]保持为0}// 读入n-1条边，构建树的无向图for(inti=1;i<n;i++){scanf("%d%d",&a,&b);e[a].push_back(b);e[b].push_back(a);}// 从根节点（第一个黑色节点）开始DFS，计算每个节点的子树中黑色节点数量dfs(root,0);// 统计所有子树中包含黑色节点的节点数（即vis[i] > 0的节点）for(inti=1;i<=n;i++)ans+=bool(vis[i]);// 如果vis[i] > 0则加1，否则加0// 输出最少操作次数：需要变黑的白色节点数 = 包含黑色节点的节点数 - 初始黑色节点数printf("%d\n",ans-num);return0;}各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
