专栏文章

题解：P11529 [THUPC 2025 初赛] 辞甲猾扎

TTmbcan
P11529题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minral0f
此快照首次捕获于
2025/12/02 07:04
3 个月前
此快照最后确认于
2025/12/02 07:04
3 个月前
查看原文
想了两年半砸贪心。

思路

设与黑点相邻，且不为黑点的点集为 SS。
不难发现答案上界是 ∣S∣|S|。
如果对于两个点 i,j∈Si,j \in S，存在 (u,i)(u,i) 和 (u,j)(u,j)，那么我们有可能通过选择 uu 作为白点来优化答案。
实际我们要做的工作是使得 ∀i∈S\forall i \in S，ii 为白点或者与一个白点相邻。
于是，我们在树上先删去所有黑点，再删去所有不属于 SS 且与 SS 中的点不相邻的点。
操作完后整个图变成了森林，我们要在这个森林上对 SS 做类似最小支配集的东西。
考虑我们怎么对一个树做最小支配集。从叶子向上贪心，如果一个点 uu 没有被支配且没在支配集中，那么将 faufa_u 放入支配集中，这样可以使得 fafaufa_{fa_u} 也被支配那么答案一定不劣。
我们在森林上做上面的过程就可以了，只不过条件变为只要 SS 被支配即可。

代码

CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...