# 两色徽章题解

## 解法比较

出题人解法使用带异或关系的并查集：到根的异或值表示相对颜色，合并时统计两种相对颜色的人数；同一集合内的新关系用于判定矛盾。每个连通块可整体翻色，因此全局最优值为各块较大一侧人数之和。不变量和证明见下文。

并查集使用路径压缩和按秩合并，时间为 $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)$ .