P6691 选择题 — 思路与复杂度

把题目翻译成图论

每个选项 i 的内容是"第 a_i 个选项是正确/错误的"。令答案为一个布尔数组 y（y[i]=1 表示第 i 个选项正确）。第 i 个选项本身正确当且仅当它所说的那句话为真， 即：

• opt=1（"第 a_i 个正确"）：y[i] = y[a_i]；
• opt=0（"第 a_i 个错误"）：y[i] = 1 - y[a_i]。

两条约束都可以写成异或形式 y[i] XOR y[a_i] = 1 - opt。因此每个选项给出一条连接 i 与 a_i 的带"同/异"标记的边，问题变成：给这个图黑白染色（满足每条边的同/异要求）， 统计合法染色数，并求最大/最小黑点数。

关键观察：每个点出度恰为 1

因为第 i 个选项只约束 a_i，所以每个点恰好有一条出边 → 这是一个函数图： 每个弱连通分量恰好含一个环，外面挂一些"指向环"的树。整张图共 n 点 n 边。

对一个弱连通分量，只要它是可染色的，固定其中一个点的颜色后其它点全部被唯一确定； 又因为所有约束都是"相等/相反"这种对全局反转不变的对称关系，所以可染色分量恰好有 2 种答案 （互为反色）。因此：

• 合法答案总数 = 2^(连通分量个数)，对 998244353 取模。

求最多 / 最少的正确选项数

每个分量中，两种染色互为反色。设某个分量大小为 s，其中一种染色有 k 个黑点 （把根的色定成 0 时统计），则另一种有 s-k 个黑点。因为不同分量间独立，逐分量贪心即可：

• 最多正确数 = 每个分量取 max(k, s-k) 之和；
• 最少正确数 = 每个分量取 min(k, s-k) 之和。

若某个分量出现矛盾（同一边要求既同又异，或奇环上的异号边不满足），则输出 No answer。

实现

用**带权并查集（奇偶并查集）**维护每个点相对集合根的异或值：

• unite(i, a, 1-opt)：要求在根相同集合时检查 parity[i] XOR parity[a] == 1-opt； 不同集合时按秩合并，并设置新子树根的 parity。
• 结束后对所有点做一次 find 压缩，每个根就是连通分量代表。
• 对每个根，cnt0 = 该分量内 parity==0 的点数（即把根色设 0 时的黑点数）， 另一种有 s-cnt0 个。

复杂度

• 时间：O(n α(n))（路径压缩 + 按秩合并），n ≤ 10^6 轻松通过。
• 空间：O(n)（parent / sz / parity / cnt0 四个数组）。

这题教了什么

把"选项的自指描述"转成同/异约束、识别出函数图的"每分量恰一环一树"结构、 用奇偶并查集做二染色（同时检测冲突），以及"每个可染色分量的两种解互为反色"这条 用来归纳计数和极值的性质。