儋州网站建设培训学校如何设立官方网站

儋州网站建设培训学校,如何设立官方网站,招聘网站建设维护人员,石家庄免费建站模板​欢迎大家订阅我的专栏#xff1a;算法题解#xff1a;C与Python实现#xff01; 本专栏旨在帮助大家从基础到进阶 #xff0c;逐步提升编程能力#xff0c;助力信息学竞赛备战#xff01; 专栏特色 1.经典算法练习#xff1a;根据信息学竞赛大纲#xff0c;精心挑选…​欢迎大家订阅我的专栏算法题解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_i0ai​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#【代码详解】#includebits/stdc.husingnamespacestd;constintN100005,MN*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){ints0;// 统计子节点中黑色节点的数量// 遍历当前节点的所有邻居for(intih[u];i!-1;ine[i]){intje[i];// 邻居节点if(jfa)// 如果是父节点跳过{continue;}// 递归处理子树dfs(j,u);// 累加子节点的颜色sa[j];}// 关键条件判断// 1. s 0: 当前节点至少有一个黑色子节点// 2. a[u] 0: 当前节点是白色if(s!a[u]){ans;// 答案加1a[u]1;// 将当前节点染成黑色}}intmain(){// 输入节点数cinn;// 初始化邻接表memset(h,-1,sizeof(h));// 输入每个节点的初始颜色for(inti1;in;i){cina[i];}// 输入n-1条边构建树for(inti1;in;i){intu,v;cinuv;add(u,v);// 添加无向边add(v,u);}// 从任意一个黑色节点开始DFSfor(inti1;in;i){if(a[i]1)// 找到第一个黑色节点{dfs(i,0);// 从该节点开始DFS父节点为0break;}}// 输出答案coutansendl;return0;}【运行结果】5 0 1 0 1 0 1 2 1 3 3 4 3 5 2