企业官网建设流程全解析

CodeForces 1290C Prefix Enlightenment 是我刷过的题里面，把"每个灯最多出现在两个集合里"这个条件用得最漂亮的一道。第一眼看到"翻转灯"和"前缀"两个词，我本能地往差分、贪心、区间数据结构上去想，结果研究了半天讨论区，发现正解居然是一棵带权并查集，而且代码量比我想象中小得多。如果你也卡在这题上，大概率不是并查集不会写，而是没有把"选集合"这件事抽象成变量。这篇文章就沿着我的思路展开：先把题意压缩成"选哪些集合"的问题，再讲清楚异或方程组是怎么被并查集维护的，最后给一份可以直接提交的 Python 代码。

1. 先把题意彻底翻译成人话

1.1 题目在问什么，以及那句"最多出现在两个集合"的分量

题目本身不复杂。你有 n 个灯，初始状态是一个 01 串，1 表示亮，0 表示灭。然后给你 k 个集合，每个集合里装的是灯的编号。一次操作就是挑一个集合，把这个集合里所有灯的状态全部反转，亮变灭，灭变亮。现在对于每个前缀位置 i，你需要回答：只用若干次操作，能不能让第 1 到第 i 盏灯全部变亮，并且总操作次数最少是多少。每个前缀是独立的问题，也就是说你在回答前缀 i 的时候，不用考虑前缀 i-1 的操作选择。

这个描述本身没什么特殊的，真正特殊的是后面这句：每个灯最多出现在两个集合里。这句话几乎是整道题的命门。如果没有这个限制，一盏灯可能属于很多个集合，那它最终变亮与否就和很多个"选不选集合"的决定纠缠在一起，问题就变成解一个一般性的 XOR 方程组，得上高斯消元，而且还要支持动态询问，复杂度会非常难看。正因为每个灯最多关联两个集合，每个灯带来的约束就只牵涉两个变量，这才有可能用并查集这种结构去维护。

我一开始没重视这句话，先去想怎么模拟翻转，走了不少弯路。后来才意识到，操作的顺序根本不重要，重要的是"哪些集合被选择了奇数次"。

1.2 前缀询问为什么可以"一边扫一边答"

还有一个容易让人困惑的点：题目问的是每个前缀独立的最小值，理论上你可以对每个前缀都重新求一次答案，那复杂度肯定爆炸。但这里有个关键性质：前缀 i 的约束只包含前 i 盏灯。

当你扫描到第 i 个位置的时候，你往约束系统里加入的恰好是前 i 盏灯各自产生的约束，后边的灯一个都没加进来。所以扫描到第 i 位时，当前这个约束系统描述的就是前缀 i 的全部限制。前缀 i+1 只不过是在这个系统上再多加一条约束而已。这天然支持增量维护：每处理一盏灯，往并查集里加一条边，同时把全局答案改一改，输出当前的答案，就是这个前缀的答案。

很多题解没把这个"扫描位置 == 约束集合大小"的点讲透，我在这里先把它点出来，后面所有的代码都是围绕这个增量过程展开的。

2. 核心建模：每个集合变成一个 0/1 变量

2.1 一盏灯的最终状态怎么写

把每个集合看成一个有选择状态的变量：

• x[j] = 0表示不选集合 j
• x[j] = 1表示选集合 j，或者说这个集合被操作了奇数次

题目里一次操作是翻转一个集合里的所有灯，那么连续操作一个集合两次等于没操作，所以我们在意的是操作次数的奇偶性。因此一个有 m 个灯、被集合 a 和 b 包含的灯 v，它的最终状态是：

初始状态 s[v] ^ x[a] ^ x[b]

如果灯 v 只属于集合 a，那就是s[v] ^ x[a]；如果哪个集合都不属于，那它永远等于s[v]。这个式子其实不需要复杂的推导，用异或看就行：每选一次包含灯 v 的集合，灯 v 的状态就翻转一次，翻转偶数次等于没翻转。

要让灯 v 最终是亮的，也就是最终状态等于 1，那么有：

s[v] ^ x[a] ^ x[b] = 1

移项一下，得到灯 v 对变量提出的要求：

x[a] ^ x[b] = 1 ^ s[v]

我们把右边的值统一记为need，它要么是 0，要么是 1。每个灯 v 就对应一个约束方程，方程左边是它所属的集合变量异或在一起。

2.2 三种情况对应三类约束

按"灯属于几个集合"分类，正好有三种：

• 不属于任何集合：没有变量参与到翻转里，只有s[v] = 1的时候这个灯才能亮。这种情况题目数据的保证会兜底，代码里直接跳过。
• 只属于一个集合 a：约束退化成x[a] = need，也就是一个变量被固定为某个值。
• 属于两个集合 a、b：约束是x[a] ^ x[b] = need。如果need = 0，要求两个变量相等；如果need = 1，要求两个变量不等。

所以整个问题就变成了：有 k 个 0/1 变量，有 n 条约束，每条约束要么把一个变量固定成某个值，要么连接两个变量要求它们相等或不等。然后要给每个前缀求一个满足所有约束的赋值方案，使得被选中的集合数量（也就是值为 1 的变量数量）最小。

建模到这里，题目的"灯"已经完全不重要了，剩下的就是一个纯代数问题。

2.3 一组约束的几何直观：带着权值的图

如果我们把每个集合看成一个点，那么每条"两个变量"的约束就是两个点之间的一条边，边上的权是need，代表两个端点取值是否相同。一条"固定变量 a 为 val"的约束，可以理解成点 a 和一个特殊"常量点"之间有一条边，这个常量点的值永远是 0。

带权并查集能维护的核心事实是：一个连通块内部，只要确定了根节点的值，其他所有节点的值就全部确定了。这是因为每条边都给出了两个点之间的异或关系，沿着树边走就能推出任意点的值。如果加入一条边之后形成了环，并且环上的异或和不为 0，那就产生矛盾，说明这组约束无解。

这道题还要求统计代价，所以光维护关系不够，还得在每个连通块里记下"根取 0 或者取 1 时，块内有多少个变量必须取 1"。

3. 带权并查集：维护"相等/不等"并同时算代价

3.1 dis 数组的语义和路径压缩

普通的并查集只能维护"两个点是否在同一集合"，但在本题里我们还需要知道"两个点之间是相等还是不等"，所以要用带权并查集。这里的"权"是一个 0/1 值。

我习惯这么定义：

fa[x] : x 的父节点 dis[x] : x 与 fa[x] 的取值异或，即 x = fa[x] ^ dis[x]

也就是说，如果dis[x] = 0，x 和它父亲取值相同；如果dis[x] = 1，x 和它父亲取值相反。路径压缩之后，dis[x]要更新成 x 与根节点的取值异或。

递归版路径压缩的关键代码是：

def find(x): if fa[x] == x: return x r = find(fa[x]) dis[x] ^= dis[fa[x]] fa[x] = r return r

这里容易写错的点是顺序：必须先递归调用find(fa[x])，此时dis[fa[x]]已经被更新成旧父节点到根的异或值，然后再把原来的dis[x]异或上去，得到的才是 x 到根的值。如果先更新fa[x]再取dis[fa[x]]，拿到的就是新父节点的值，会出错。

3.2 合并两个连通块时的推导

现在处理一条约束x[a] ^ x[b] = c。假设经过find之后，a 的根是ra，b 的根是rb，同时有：

x[a] = dis[a] ^ x[ra] x[b] = dis[b] ^ x[rb]

把这两行代入约束：

dis[a] ^ x[ra] ^ dis[b] ^ x[rb] = c

整理成根之间的关系：

x[ra] ^ x[rb] = dis[a] ^ dis[b] ^ c

记d = dis[a] ^ dis[b] ^ c，含义就是：x[rb] = x[ra] ^ d。合并时把rb的父节点设成ra，同时把dis[rb]设成d即可：

fa[rb] = ra dis[rb] = d

这一步推导是整个题解的核心，很多代码直接写了unite(a, b, c)，但如果不理解 d 是怎么来的，写错一个符号都很难查。我强烈建议自己推一遍这个式子。

3.3 连通块的代价怎么算：cnt 与 fixed

光有关系还不够，还得在每个时刻知道"当前约束系统的最小操作次数"。

对每个连通块，我们记录以根为基准的两种代价：

• cnt0[root]：根取 0 时，这个连通块内有多少个变量必须取 1
• cnt1[root]：根取 1 时，这个连通块内有多少个变量必须取 1

因为每个变量取 1 就意味着对应的集合被选择了，要付 1 次操作代价。

初始化时，每个集合单独成一个连通块，根就是它自己：

• cnt0[i] = 0，根取 0 时自己取 0，代价 0
• cnt1[i] = 1，根取 1 时自己取 1，代价 1

合并两个连通块时，假设新根是ra，关系是d = dis[rb]。如果d = 0，那么rb与ra同值；如果d = 1，则反值：

if d == 0: cnt0[ra] += cnt0[rb] cnt1[ra] += cnt1[rb] else: cnt0[ra] += cnt1[rb] cnt1[ra] += cnt0[rb]

这个式子的意思很直观：当新根取 0 时，rb的值已经由d唯一确定，rb所在块内所有取 1 的变量数就是对应那一项的cnt，直接累加。

此外还要处理"固定值"约束。初始化时给每个根记一个fixed[root]，取值为-1/0/1：

• -1表示根的值还没被确定
• 0或1表示根被固定成这个值

当固定约束出现时，我们先找到a的根root，要固定变量a为val。由x[a] = dis[a] ^ x[root]可得根的值应该是val ^ dis[a]，于是调用set_root_fix(root, val ^ dis[a])。

一个连通块的贡献是这样算的：

cost(root) = cnt0[root] 如果 fixed[root] == 0 = cnt1[root] 如果 fixed[root] == 1 = min(cnt0, cnt1) 如果没有固定

固定值的意义在于，一旦根被固定，这个连通块就失去了自由选择的余地，代价不再取 min，而是取被固定那一种的值。全局答案就是所有根cost的和。

4. 逐个前缀增量更新：答案是怎么顺出来的

4.1 灯属于 0 个、1 个、2 个集合时的处理

现在从左往右扫灯，每扫到一盏灯，就往并查集里加这条灯带来的约束，然后立刻输出当前全局答案。

设当前灯 i 的初始状态是s[i]，先算need = 1 ^ s[i]，也就是"灯要变亮，需要关联的集合变量异或出什么值"。

三种情况：

1. belong[i]为空：灯不受任何集合控制。如果s[i] == 1，它本来就是亮的，什么也不用做；如果s[i] == 0，那它永远没法亮。题目数据保证每个前缀都有解，所以这种情况要么不出现，要么灯本来就是亮的，代码里跳过即可。
2. belong[i]只有一个集合 a：调用set_root_fix固定变量 a 的值为need。
3. belong[i]有两个集合 a、b：调用unite(a, b, need)，让x[a] ^ x[b] = need。

注意这里不用真的去管第 i 盏灯后面的灯，因为后面的约束还没加进来，这个系统恰好就是前缀 i 的约束系统。

4.2 合并时的全局答案更新公式

全局答案不是每次重算的，而是在合并操作里增量维护。每次unite(a, b, c)之前，先减去两个根各自的cost：

ans -= cost(ra) + cost(rb)

合并完之后，再把新根的cost加回去：

ans += cost(ra)

set_root_fix也一样，先把该根的旧cost减掉，更新fixed之后再加新cost。这样每次操作的更新量是 O(1) 的，加上并查集本身的find代价，整道题的复杂度就是 O((n+k) α(n+k))。

这个"先减后加"的思路很基础，但特别容易忘。我一开始只想着维护cnt，忘了更新全局ans，结果样例都过不了。

4.3 手推一个 3 灯 2 集合的完整样例

拿一个小样例完整走一遍，比空谈公式直观得多。

n = 3, k = 2 s = 010 S0 = {1, 2} S1 = {2, 3}

三个灯带来的约束：

• 灯 1：只在集合 S0，s = 0，所以x0 = 1
• 灯 2：在 S0、S1，s = 1，所以x0 ^ x1 = 0
• 灯 3：只在集合 S1，s = 0，所以x1 = 1

初始化后每个集合都是独立根：cnt0 = 0, cnt1 = 1，每个根的fixed = -1，所以每个根的cost = min(0, 1) = 0，全局ans = 0。

处理灯 1，固定x0 = 1：

• 根是 0，先减cost(0) = 0
• 设置fixed[0] = 1
• 再加cost(0) = cnt1[0] = 1
• ans变成 1，输出 1

处理灯 2，约束x0 ^ x1 = 0：

• ra = 0, rb = 1
• 先减cost(0) + cost(1) = 1 + 0 = 1，ans变成 0
• 计算d = dis[0] ^ dis[1] ^ 0 = 0
• 合并后cnt0[0] = 0 + 0 = 0，cnt1[0] = 1 + 1 = 2
• 此时fixed[0]仍然是 1，所以新根cost(0) = cnt1[0] = 2
• ans变成 2，输出 2，对应x0 = 1, x1 = 1，两个集合都被选，代价 2

处理灯 3，固定x1 = 1：

• find(1)得到根 0，且dis[1] = 0，也就是x1 = x0
• 需要固定根 0 的值为need ^ dis[1] = 1 ^ 0 = 1
• fixed[0]已经就是 1，先减cost(0) = 2，再加回2，ans不变，输出 2

最终答案是1 2 2，和预期完全一致。

5. 完整实现与提交前检查

5.1 代码逐段拆解

下面是我整理的完整 Python 提交版。为了在 Codeforces 上稳妥运行，我把递归深度开大了一点，并查集的 find 用的是递归写法，路径压缩后深度基本是常数，不会真的递归到底。

import sys sys.setrecursionlimit(300000) def solve(): input = sys.stdin.readline n, k = map(int, input().split()) s = input().strip() belong = [[] for _ in range(n)] for i in range(k): arr = list(map(int, input().split())) for v in arr[1:]: belong[v - 1].append(i) fa = list(range(k)) dis = [0] * k cnt0 = [0] * k cnt1 = [1] * k fixed = [-1] * k def find(x): if fa[x] == x: return x r = find(fa[x]) dis[x] ^= dis[fa[x]] fa[x] = r return r def cost(root): if fixed[root] == 0: return cnt0[root] if fixed[root] == 1: return cnt1[root] return min(cnt0[root], cnt1[root]) ans = 0 def set_root_fix(root, val): nonlocal ans ans -= cost(root) if fixed[root] == -1: fixed[root] = val # 如果 fixed[root] 已有值且与 val 不同，说明矛盾 # 本题数据保证不会发生，所以这里不额外处理 ans += cost(root) def unite(a, b, c): nonlocal ans ra, rb = find(a), find(b) if ra == rb: return ans -= cost(ra) + cost(rb) d = dis[a] ^ dis[b] ^ c fa[rb] = ra dis[rb] = d if d == 0: cnt0[ra] += cnt0[rb] cnt1[ra] += cnt1[rb] else: cnt0[ra] += cnt1[rb] cnt1[ra] += cnt0[rb] if fixed[rb] != -1: req = fixed[rb] ^ d if fixed[ra] == -1: fixed[ra] = req # 同理，冲突数据不会出现 ans += cost(ra) res = [] for i in range(n): need = 1 - (ord(s[i]) - 48) if len(belong[i]) == 0: pass elif len(belong[i]) == 1: a = belong[i][0] ra = find(a) set_root_fix(ra, need ^ dis[a]) else: a, b = belong[i][0], belong[i][1] unite(a, b, need) res.append(str(ans)) print(" ".join(res)) if __name__ == "__main__": solve()

这份代码的输入格式是：第一行 n、k，第二行 s，接下来 k 行每行是集合大小加集合内灯的编号。集合编号从 0 开始，灯的编号从 1 开始，读入时要减一。

5.2 三个容易踩的坑

第一个坑是dis数组的含义混淆。不同人的写法定义可能相反，有的是"x 到父节点的异或"，有的是"父节点到 x 的异或"。这本身无所谓，但一旦确定了就得在每个合并公式里保持一致。我推导的时候用的是x = fa[x] ^ dis[x]，合并公式d = dis[a] ^ dis[b] ^ c是配合这个定义算出来的，如果你按别的博客的代码抄，但find里的更新顺序不同，很可能就错了。

第二个坑是固定值合并时忘记处理。两个连通块合并的时候，如果rb那边已经有fixed值，这个固定信息不能丢，要换算成新根的固定值，也就是req = fixed[rb] ^ d。我第一版代码只合并了cnt和fa，没管fixed，结果某个测试点里前缀答案突然少了一块代价。

第三个坑是遇到ra == rb直接返回时，没有检查这条约束是否真的满足。如果dis[a] ^ dis[b] == c，那这条边在环上没有矛盾，返回没问题；如果不等于c，说明这个前缀无解。题目数据保证每个前缀有解，所以这里可以直接返回。但为了调试方便，我建议在本地写一个断言，万一自己造数据造出矛盾，能第一时间发现。

5.3 复杂度分析与能过的常数

复杂度在上文已经说过，每个灯最多触发一次find加一次合并，并查集操作近似 O(1)，所以总复杂度是 O((n + k) α(n+k))，空间 O(n + k)。n 和 k 都是 3e5 量级，Python 在这道题上是能过的。

从常数角度提两个小优化。第一，别在循环里重复len(belong[i])这种调用，一次取出来存成变量；第二，ord(s[i]) - 48比int(s[i])快，因为省去了字符串解析的开销。这些在 3e5 的数据量下看起来微不足道，但 Codeforces 的 Python 时间限制不会给太多余地，能省一点是一点。

6. 这类题的识别信号与延伸思考

6.1 什么时候应该想到带权并查集

经过这题你会发现，带权并查集的适用场景有很强的信号特征。最显眼的就是"每个元素最多出现在两个集合里"这句话。它本质上是告诉你：每个约束方程最多涉及两个变量。当约束方程都是x_a ^ x_b = c这种二元形式时，你完全可以把方程看成图上的边，把"维护方程组是否有解、求某个最优解"转化成"动态维护图的连通性和边权一致性"。

另一个信号是题目要求多组前缀询问，但每个前缀只比前一个多一条约束。这几乎是在明示你可以增量维护：每次加一条边，更新一下全局统计量。如果题目改成任意区间询问，那就需要可撤销并查集或者离线分治，难度会高一个档次。

6.2 与 2-SAT、XOR 方程组的关系

把这道题和 2-SAT 放在一起看很有意思。2-SAT 的子句是两个文字用"或"连接，而这里的两条约束是"两个变量异或等于 0 或 1"。它们都是二元的，但语义不同。其实这道题更本质的模型是 GF(2) 上的线性方程组：

x_a + x_b = c (mod 2)

因为每个方程只涉及两个变量，所以可以用图来建模，并查集维护的就是"沿着路径异或起来是否一致"。这也是为什么它不需要高斯消元：高斯消元适合变量之间约束稠密的情况，而这里方程数虽然多，但每个方程的度数只有 2，图是稀疏的，并查集是天然适配的数据结构。

更进一步说，如果题目改成"每个灯最多出现在三个集合里"，那约束就变成三元异或，并查集就不够用了。三元异或约束对应的是三维向量空间的线性相关性问题，维护起来复杂得多。所以"最多两个集合"这个看似不起眼的限制，直接决定了算法的选型。

6.3 一点个人经验

我自己刚做这题的时候，第一反应是建图跑 2-SAT，因为"每个灯最多两个集合"很像 2-SAT 里每个变量出现两次的样子。后来发现 2-SAT 求的是存在性，而这题要的是带权的最小代价，还得支持前缀增量，于是又卡了一阵。最后看懂了带权并查集的做法，有种"原来如此"的感觉。

说实话，这题最值的不是并查集本身，而是那种"把题目条件翻译成变量方程"的思维方式。后面我遇到不少题，都会先问自己一句：题目里的每个对象到底在约束什么？这个约束是几元的？如果是二元的，很多问题都能用图或者并查集解决。顺手一提，这场 Div.1 的 F 题 Artistic Partition 也是我觉得很值得琢磨的题，和本题是完全不同的两个方向，有空我们可以再单独聊。这题如果只是看懂题解，可能过几天就忘，但如果自己动手把推导走一遍、把样例手推一遍，再改几处代码试试错误会发生什么，它的价值才能真正长在你身上。