题意
有一个长度为 \(n\) 的 \(01\) 数组 \(a\)。
给出 \(q\) 组限制条件，第 \(i\) 组给出大小为 \(k_i\) 的集合 \(C_i=\{x_{i,1},x_{i,2},\cdots,x_{i,k_i}\}\)。若 \(cnt_0\) 为 \(\{x|x\in C_i,a_x=0\}\) 的集合大小，\(cnt_1\) 为 \(\{x|x\in C_i,a_x=1\}\) 的集合大小，则保证 \(|cnt_0-cnt_1|\le 1\)。
且保证若存在 \(i\neq j,x,y,z\) 有 \(x\in C_i,x\in C_j,y\in C_i,z\in C_j\)，则有 \(y\in C_j\) 或 \(z\in C_i\)。
求出一组可能的 \(a\)，或判断无解。
思路
由题意得，对于两个不同的集合 \(C_i,C_j\pod{i\neq j}\)，只可能存在不交和包含的关系。
将限制条件按照大小排序，我们便可以把限制条件表示为一棵树的关系，每个节点分为它的子节点和下面没有包含的颜色部分，如下图：
其中黑色部分表示这个限制条件包含的节点，红色部分表示下面没有包含的颜色部分。
可以发现，如果限制条件的长度为偶数，那么就只有一半 \(0\) 一半 \(1\) 的填法，但是如果为奇数，那么就可以多填一个 \(0\) 或者多填一个 \(1\)。
于是对于每个限制条件，让它的所有长度为奇数的子节点以多一个 \(0\) 和多一个 \(1\) 的形式交错，最后再确定自己的红色部分即可。
代码
#include <bits/stdc++.h>
using namespace std;
int n,m,a[1000005],id[1000005],be[1000005],tp[1000005];
vector<int> t[1000005],e[1000005];
bool cmp(int x,int y){return t[x].size()>t[y].size();
}
void dfs(int x,int mr){vector<int> mc;for(int v:t[x])if(be[v]==x) mc.push_back(v);for(int v:e[x]){if(t[v].size()%2==1){if(mr==1) dfs(v,1);else dfs(v,0);mr^=1;}elsedfs(v,0);}int c=0;if(mc.size()%2==0){for(int v:mc){c++;if(c<=mc.size()/2) a[v]=0;else a[v]=1;}}else{for(int v:mc){c++;if(c==mc.size()) a[v]=mr;else if(c<=mc.size()/2) a[v]=0;else a[v]=1;}}
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>n>>m;for(int k,i=1;i<=m;i++){cin>>k,id[i]=i;for(int x,j=1;j<=k;j++)cin>>x,t[i].push_back(x);}sort(id+1,id+1+m,cmp);for(int i=1;i<=m;i++){if(!be[t[id[i]][0]])e[0].push_back(id[i]);elsee[be[t[id[i]][0]]].push_back(id[i]);for(int v:t[id[i]])be[v]=id[i];}dfs(0,0);for(int i=1;i<=n;i++)cout<<a[i]<<" ";return 0;
}
