种类并查集

对于某些需要分类合并的问题，可以使用种类并查集.

例如这道 ，去年NUAA组队选拔的一道原题。

把所有元素分为三类，然后把并查集的数组开三倍，每一倍数组都存相对于自己的其它类的哨兵元素。

很抽象是吧. 其实这玩意完全可以用带权并查集替代.

带权并查集

我们知道并查集是一种森林结构. 如果往所有连边上增加权值, 就是带权并查集了~

如何把权值和种类联系起来呢? 我们考虑使用剩余类

剩余类是一种从 $\mathbb{Z} \rightarrow \mathbb{Z}_n$ 的同态映射: $f(x) = x % n$, 映射值相同的放在同一类.

而定义后者的运算是模$n$加 $\oplus_n$, 这就代表了权值的关系.

例如 $f(a)=2,f(b)=0,n=3$, 就代表$a$向$b$连一条权值为$dis[a,b]=1$的边.

路径压缩

定义 $\mathrm{val}_i$ 为点i到其父亲的权值, 那么每次find()只需把父亲的 $\mathrm{val}$ 与自己的做下运算即可.

合并

假设$a$—>$fa$, $b$—>$fb$, 我们令 $fa[fa] = fb$, 然后根据 $val[a] \oplus val[fa] = dis[a,b] \oplus val[b]$ 修改 $val[fa]$

其余题目

背包dp结合