题解：P13583 [NWRRC 2023] Colorful Village

题意

有一个节点数为

2n

的树。每个节点有一个颜色，一共

n

种颜色，每种颜色各有

2

个对应节点。在树上找一个大小为

n

的连通块，要求其中恰好包含每种颜色的节点各

1

个。

思路

记

a_i

表示第

i

个节点是否被选入集合内，

1

代表选入。

任意位置的连通块并不好做，所以我们考虑枚举第

1

种颜色所选的节点

u

强制加入集合内。令

u

为根，则连通块可以看作到根节点的连通性。

此时所有的要求条件可以看作如下集中限制：

强制 $u$ 加入集合，即强制 $a_u=1$ ；
连通性：设 $p$ 为 $q(q\neq u)$ 在树上的父亲节点，则有 $a_q=1\longrightarrow a_p=1$ 和 $a_p=0\longrightarrow a_q=0$ ；
每种颜色各 $1$ 个节点：设 $x$ 和 $y$ 为颜色相同的两个节点，则有 $a_x \oplus a_y=1$ 。

上述限制都可以用 2-SAT 解决。

做两次 2-SAT 即可，时间复杂度

O(n)

。

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,c[200005],w[100005][2],ans[100005],tot;
vector<int> edget[200005];
void addt(int u,int v){edget[u].push_back(v);}
vector<int> edge[400005];
void add(int u,int v){edge[u].push_back(v);}
void dfst(int u,int fa){
	for(int i=0,in=edget[u].size();i<in;i++){
		int v=edget[u][i];
		if(v!=fa)add(2*n+u,2*n+v),add(v,u),dfst(v,u);
	}
}
int lo[400005],xh[400005],dfn,h[400005],toth;
int z[400005],zd,us[400005];
void dfs(int u){
	lo[u]=xh[u]=++dfn,z[++zd]=u,us[u]=1;
	for(int i=0,in=edge[u].size();i<in;i++){
		int v=edge[u][i];
		if(!xh[v])dfs(v),lo[u]=min(lo[u],lo[v]);
		else if(us[v])lo[u]=min(lo[u],xh[v]);
	}
	if(lo[u]==xh[u]){
		++toth;
		while(z[zd]!=u)h[z[zd]]=toth,us[z[zd]]=0,--zd;
		h[z[zd]]=toth,us[z[zd]]=0,--zd;
	}
}
bool sat(int x){
	for(int i=1;i<=4*n;i++)edge[i].clear();
	add(2*n+x,x);
	dfst(x,0);
	for(int i=1;i<=n;i++){
		int u=w[i][0],v=w[i][1];
		add(u,2*n+v),add(2*n+u,v);
		add(v,2*n+u),add(2*n+v,u);
	}
	for(int i=1;i<=4*n;i++)lo[i]=xh[i]=0;
	dfn=toth=0;
	for(int i=1;i<=4*n;i++)if(!xh[i])dfs(i);
	for(int i=1;i<=2*n;i++)if(h[i]==h[i+2*n])return false;
	tot=0;
	for(int i=1;i<=2*n;i++)if(h[i]<h[i+2*n])cout<<i<<' ';
	cout<<'\n';
	return true;
}
void work(){
	cin>>n;
	for(int i=1;i<=n;i++)w[i][0]=w[i][1]=0;
	for(int i=1;i<=2*n;i++){
		cin>>c[i];
		if(w[c[i]][0]==0)w[c[i]][0]=i;else w[c[i]][1]=i;
	}
	for(int i=1;i<=2*n;i++)edget[i].clear();
	for(int i=1;i<2*n;i++){
		int u,v;cin>>u>>v;
		addt(u,v),addt(v,u);
	}
	bool check;
	check=sat(w[1][0]);
	if(check)return;
	check=sat(w[1][1]);
	if(check)return;
	cout<<-1<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;cin>>T;
	while(T--)work();
}

题解：P13583 [NWRRC 2023] Colorful Village

文章操作

题意

思路

相关推荐

评论

题解：P13583 [NWRRC 2023] Colorful Village