企业官网建设流程全解析

P11529 [THUPC 2025 初赛] 辞甲猾扎

题目描述

给你一棵n nn个点的无根树，有k kk个点初始为黑色，其余点初始为灰色，你可以在一开始将一些灰色点染成白色。染完后，现在进行如下操作，直到树上不存在灰色点。

每一轮对所有灰色点同时进行如下操作：

1. 检查与该灰色点u uu直接相连的点有没有黑色或白色点，如果没有，则u uu保持灰色。
2. 如果与u uu直接相连的点有白色点，则u uu变为白色。
3. 如果与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 n+23∼n+2行每行两个整数u , v ( 1 ≤ u , v ≤ n ) u,v\;(1\le u,v\le n)u,v(1≤u,v≤n)，代表一条树上的边。

输出格式

一行一个整数，为答案。

输入输出样例 #1

输入 #1

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

输出 #1

1

输入输出样例 #2

输入 #2

10 3 1 6 8 1 2 2 3 3 4 4 5 4 6 5 7 5 8 6 9 7 10

输出 #2

3

说明/提示

• 对于第一组样例，一开始将2 22号点染白即可
• 对于第二组样例，一开始将3 , 4 , 9 3,4,93,4,9号点染白为满足条件且数量最小一组方案

题目来源

来自 2025 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2025）初赛。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2025pre/tree/master 查看。

C++实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intread(){intx=0,f=1;charc=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();returnx*f;}namespacetokido_saya{constintmaxn=1e6+5;structedge{intnext,to;}e[maxn*2];inth[maxn],cnt,f[maxn][4],n,k,b[maxn],nr[maxn],ans;voidaddedge(intx,inty){e[++cnt].next=h[x],e[cnt].to=y,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(inti=h[u];i;i=e[i].next){intv=e[i].to;if(v==fa)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;n=read(),k=read();for(inti=1;i<=k;i++)x=read(),b[x]=1;for(inti=1;i<n;i++){x=read(),y=read();addedge(x,y),addedge(y,x);}for(intu=1;u<=n;u++)if(b[u])for(inti=h[u];i;i=e[i].next){intv=e[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考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容