打卡信奥刷题（3591）用C++实现信奥题 P11562 【MX-X7-T3】[LSOT-3] 寄存器

P11562 【MX-X7-T3】[LSOT-3] 寄存器题目背景原题链接https://oier.team/problems/X7D。这里不是 APIO所以这个题也不是让你手搓 CPU。题目描述有n nn个寄存器编号为1 ∼ n 1 \sim n1∼n。这些寄存器由n − 1 n-1n−1条带有开关的电线连接。为了保证交换信息的顺利保证每两个寄存器都可以通过若干条电线连接。初始时每个寄存器存储的信息都是0 00。小 H 每次可以独立地操纵所有电线的开关然后选择一个寄存器通电。若一个寄存器与一个通电的寄存器有开启的电线相连则这个寄存器也会通电。所有通电的寄存器都会反转存储的信息0 00会变成1 111 11会变成0 00。小 H 想让寄存器存储他想要的信息他希望你告诉他最少需要进行多少次通电。输入格式第一行一个正整数n nn表示寄存器个数。第二行n nn个非负整数a 1 , … , a n a_1, \ldots, a_na1​,…,an​表示小 H 希望寄存器i ii存储a i a_iai​。保证a i a_iai​为0 00或1 11。接下来n − 1 n - 1n−1行每行两个正整数u , v u, vu,v表示寄存器u uu和v vv之间有一根电线。保证每两个寄存器都可以通过若干条电线连接。输出格式仅一行一个非负整数表示最少进行多少次通电。输入输出样例 #1输入 #15 1 0 0 1 0 1 2 2 3 2 4 3 5输出 #12输入输出样例 #2输入 #215 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 10 2 1 7 1 5 9 7 14 2 4 11 6 5 9 15 4 5 5 3 5 14 13 5 5 8 5 12输出 #24说明/提示【样例解释 #1】先将电线( 1 , 2 ) (1, 2)(1,2)关闭其余开启给寄存器1 11通电此时1 11的信息翻转所有寄存器存储的信息变为1 0 0 0 0。然后将电线( 2 , 4 ) (2, 4)(2,4)关闭其余开启给寄存器4 44通电此时4 44的信息翻转所有寄存器存储的信息变为1 0 0 1 0满足要求。可以证明不存在更优的方案。【数据范围】本题采用捆绑测试。子任务 120 分n ≤ 5 n\le 5n≤5。子任务 220 分对于第i ii根电线u i uiuiv i 1 vi1vi1。子任务 330 分不存在一对相邻的寄存器希望储存的信息相同。子任务 430 分无特殊性质。对于全部的数据1 ≤ n ≤ 10 6 1\le n\le 10^61≤n≤1061 ≤ u , v ≤ n 1\le u,v\le n1≤u,v≤n0 ≤ a i ≤ 1 0 \le a_i \le 10≤ai​≤1每两个寄存器都可以通过若干条电线连接。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;intn;inta[1000005]{114514};vectorintadj[1000005];intmaxp,maxd;voiddfs(intcur,intpar,intdeep){if(a[cur]!a[par])deep;if(a[cur]1deepmaxd){maxddeep;maxpcur;}for(inti:adj[cur])if(i!par)dfs(i,cur,deep);}signedmain(){ios::sync_with_stdio(0);cin.tie(nullptr);cinn;boolnoonetrue;// 特判一波全为0for(inti1;in;i){cina[i];if(a[i]1)noonefalse;}if(noone){cout0;return0;}for(inti1;in;i){intu,v;cinuv;adj[u].push_back(v);adj[v].push_back(u);}dfs(1,0,0);maxd0;dfs(maxp,0,0);cout(maxd1)/2;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容