新高一暑假第一期集训恢复性训练【数据结构-晚测】（并查集）（补）

新高一暑假第一期集训恢复性训练【数据结构-晚测】（并查集）（补）

[CF1290C] Prefix Enlightment

带权扩展域并查集。

任意三个子集的交集为空集，显然，一个点最多只能在两个集合中出现，这样所有集合的大小之和是 \(\Theta(n)\) 的。

一个在两个集合中出现的点ii相当于连接了 \(2\) 个集合 \(u_i\) 和 \(v_i\)，这是一个图。

不妨把整张图染成选和不选两种颜色。

若 \(S_i=0\)，则 \(i\) 的状态要改变，可以发现，\(u_i\) 和 \(v_i\) 一定异色。

若 \(S_i = 1\)，则 \(i\) 的状态不变，可以发现，\(u_i\) 和 \(v_i\) 一定同色。

接下来就用扩展域并查集来做，一个颜色的点的权值是 \(0\)，另一个颜色的点的权值是 \(1\)，取并查集合并后两个集合的权值的最小值即为答案。

如果 \(i\) 在任何一个给出的集合中都未出现过，则我们无法去修改 \(Si\)，但因为题目保证有解，所以不用去管。

但若某个 \(i\) 只在一个集合中出现，怎么去强制选点？领略到了一个神奇的做法，可以建一个点权为无穷大的虚点，把该点和虚点连接。