打卡信奥刷题（3586）用C++实现信奥题 P11529 [THUPC 2025 初赛] 辞甲猾扎

P11529 [THUPC 2025 初赛] 辞甲猾扎题目描述给你一棵n nn个点的无根树有k kk个点初始为黑色其余点初始为灰色你可以在一开始将一些灰色点染成白色。染完后现在进行如下操作直到树上不存在灰色点。每一轮对所有灰色点同时进行如下操作检查与该灰色点u uu直接相连的点有没有黑色或白色点如果没有则u uu保持灰色。如果与u uu直接相连的点有白色点则u uu变为白色。如果与u uu直接相连的点有黑色点则u uu变为黑色。这个顺序说明同时与白色和黑色相邻时会被染成白色。注意此处对所有灰色点同时进行操作也就是说在这一轮被染上颜色的点不能作为其它点改变颜色的根据。现在求一开始最少染几个点为白色可以使树最终黑色点不超过k kk个。输入格式第一行两个整数n , k ( 1 ≤ n ≤ 10 6 , 1 ≤ k ≤ n ) n,k\;(1\le n\le 10^6,1\le k \le n)n,k(1≤n≤106,1≤k≤n)含义见上文。第二行k kk个整数代表一开始被染成黑色的点的标号。第3 ∼ n 2 3\sim n23∼n2行每行两个整数u , v ( 1 ≤ u , v ≤ n ) u,v\;(1\le u,v\le n)u,v(1≤u,v≤n)代表一条树上的边。输出格式一行一个整数为答案。输入输出样例 #1输入 #15 2 3 5 1 2 1 3 2 4 2 5输出 #11输入输出样例 #2输入 #210 3 1 6 8 1 2 2 3 3 4 4 5 4 6 5 7 5 8 6 9 7 10输出 #23说明/提示对于第一组样例一开始将2 22号点染白即可对于第二组样例一开始将3 , 4 , 9 3,4,93,4,9号点染白为满足条件且数量最小一组方案题目来源来自 2025 清华大学学生程序设计竞赛暨高校邀请赛THUPC2025初赛。题解等资源可在 https://gitlink.org.cn/thusaa/thupc2025pre/tree/master 查看。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;intread(){intx0,f1;charcgetchar();while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9)xx*10c-0,cgetchar();returnx*f;}namespacetokido_saya{constintmaxn1e65;structedge{intnext,to;}e[maxn*2];inth[maxn],cnt,f[maxn][4],n,k,b[maxn],nr[maxn],ans;voidaddedge(intx,inty){e[cnt].nexth[x],e[cnt].toy,h[x]cnt;}voiddfs(intu,intfa){if(b[u])f[u][0]f[u][1]f[u][2]1e9;elsef[u][0]1,f[u][1]1e9;for(intih[u];i;ie[i].next){intve[i].to;if(vfa)continue;dfs(v,u);if(!b[u])f[u][0]min(min(f[v][0],f[v][1]),min(f[v][2],f[v][3])),f[u][0]min(f[u][0],(int)1e9);if(!b[u])f[u][1]min(f[u][3]f[v][0],f[u][1]min(min(f[v][0],f[v][1]),f[v][3])),f[u][1]min(f[u][1],(int)1e9);if(!b[u])f[u][2]min(f[v][1],f[v][3]),f[u][2]min(f[u][2],(int)1e9);f[u][3]min(min(f[v][0],f[v][1]),f[v][3]),f[u][3]min(f[u][3],(int)1e9);}if(nr[u]!b[u])f[u][3]1e9;}intmain(){intx,y;nread(),kread();for(inti1;ik;i)xread(),b[x]1;for(inti1;in;i){xread(),yread();addedge(x,y),addedge(y,x);}for(intu1;un;u)if(b[u])for(intih[u];i;ie[i].next){intve[i].to;nr[v]1;}dfs(1,0);printf(%d,min(min(f[1][0],f[1][1]),f[1][3]));return0;}}intmain(){returntokido_saya::main();}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容