P11529 [THUPC 2025 初赛] 辞甲猾扎

发表于 分类于 本文字数： 1.7k 阅读时长 ≈ 2 分钟

P11529 [THUPC 2025 初赛] 辞甲猾扎

想了两年半砸贪心。

思路

设与黑点相邻，且不为黑点的点集为 。

不难发现答案上界是 。
如果对于两个点 ，存在 和 ，那么我们有可能通过选择 作为白点来优化答案。

实际我们要做的工作是使得 ， 为白点或者与一个白点相邻。

于是，我们在树上先删去所有黑点，再删去所有不属于 且与 中的点不相邻的点。
操作完后整个图变成了森林，我们要在这个森林上对 做类似最小支配集的东西。

考虑我们怎么对一个树做最小支配集。从叶子向上贪心，如果一个点 没有被支配且没在支配集中，那么将 放入支配集中，这样可以使得 也被支配那么答案一定不劣。

我们在森林上做上面的过程就可以了，只不过条件变为只要 被支配即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
const int N = 1e6+10;
int n,m,ans;
struct{
	int to,nex;
}edge[N];
int head[N],edge_num;
inline void add(int x,int y){
	edge[++edge_num].to = y;
	edge[edge_num].nex = head[x];
	head[x] = edge_num;
}
struct Edge{
	int u,v;
}ed[N];
int B[N],W[N];
int is_dfs[N],vis[N],in_st[N],fa[N];
inline void dfs(int now,int fu){
	is_dfs[now] = 1;
	fa[now] = fu;
	for(int i=head[now];i;i=edge[i].nex){
		int tto = edge[i].to;
		if(tto==fu) continue;
		dfs(tto,now);
	}
	if(!vis[now] && W[now]){
		if(!in_st[fa[now]]){
			in_st[fa[now]] = 1;
			++ans;
		}
		vis[now] = 1;
		vis[fa[now]] = 1;
		vis[fa[fa[now]]] = 1;
	}
}
int main(){
	// freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);

	read(n,m);
	for(int i=1,x;i<=m;++i){
		read(x);
		B[x] = 1;
	}
	for(int i=1,u,v;i<n;++i){
		read(u,v);
		if(B[u] && !B[v]) W[v] = 1;
		if(B[v] && !B[u]) W[u] = 1;
		if(B[u] || B[v]) continue;
		ed[i] = {u,v};
	}
	for(int i=1;i<n;++i){
		if(W[ed[i].u] || W[ed[i].v]){
			add(ed[i].u,ed[i].v);
			add(ed[i].v,ed[i].u);
		}
	}
	for(int i=1;i<=n;++i){
		if(!is_dfs[i] && W[i]){
			dfs(i,i);
		}
	}
	printf("%d",ans);

	fclose(stdin);
	fclose(stdout);
	return 0;
}