两色徽章题解¶
解法比较¶
出题人解法使用带异或关系的并查集：到根的异或值表示相对颜色，合并时统计两种相对颜色的人数；同一集合内的新关系用于判定矛盾。每个连通块可整体翻色，因此全局最优值为各块较大一侧人数之和。不变量和证明见下文。
并查集使用路径压缩和按秩合并，时间为 \(O((n+m)\alpha(n))\) ，空间为 \(O(n)\) .Codex（GPT-6）负责本题的程序实现与边界说明。
思路¶
用带奇偶关系的并查集表示每个连通分量。对每个顶点记录它到所在根的颜色异或值；对每个根记录两类顶点数量 \(c_0,c_1\) ：\(c_0\) 是与根同色的顶点数，\(c_1\) 是与根异色的顶点数。这两个下标表示相对于根的颜色关系，不是最终分配的颜色编号。
请求 \((u,v)\) 若两端已在同一分量，只有二者颜色异或值为 \(1\) 时才能接受。否则合并两个分量，并规定 \(u,v\) 的颜色不同。合并时根据两端到根的奇偶值决定是否交换其中一组的两个计数。
答案始终是各分量 \(\max(c_0,c_1)\) 之和。合并前从答案中减去两个旧分量的贡献，合并后加上新分量的贡献。拒绝请求时答案不变。孤立顶点各自贡献 \(1\) .
正确性¶
并查集不变量是：任意顶点记录的到根奇偶值等于它与根必须具有的颜色差。已连接的两点若奇偶值相同，新边要求它们异色，与现有约束冲突；否则新边不改变二分性。不同分量之间总能独立翻转颜色，使新边两端异色，合并时的计数交换恰好记录这个翻转。因此接受判定与新的两个颜色类始终正确。
每个连通分量只能整体翻转，颜色 \(0\) 最多占据该分量两个颜色类中较大的一类；不同分量的选择互不影响。逐分量求和即为所求最大值，程序在每次合并时精确更新这一和。
复杂度¶
按大小合并并进行路径压缩，每个请求的均摊时间为 \(O(\alpha(n))\) ，总时间为 \(O((n+m)\alpha(n))\) ，空间为 \(O(n)\) .