更佳的阅读体验：2023 国庆集训 Day 5A 笔记，本文同步发表于 洛谷博客。

以下内容为个人总结，如有错误或您有不同见解，欢迎指出。

并查集

• 并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

• 顾名思义，并查集支持两种操作：

  • 合并（Union）：合并两个元素所属集合（合并对应的树）。
  • 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合。
• 并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。
• 并查集无法以较低复杂度实现集合的分离。
• 初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。

查询

• 我们需要沿着树向上移动，直至找到根节点。

size_t dsu::find(size_t x) {
    return pa[x] == x ? x : find(pa[x]);
}

路径压缩

size_t dsu::find(size_t x) {
    return pa[x] == x ? x : find(pa[x]);
}

合并

• 要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。

void dsu::unite(size_t x, size_t y) {
    pa[find(x)] = find(y);
}

启发式合并

• 启发式合并 + 路径压缩：$O(m\alpha)$。
• 不使用启发式合并、只使用路径压缩的最坏时间复杂度是 $O(m \log n)$ 。不使用启发式合并、只使用路径压缩，在平均情况下，时间复杂度依然是 $O(m\alpha(m, n))$。
• 如果只使用启发式合并，而不使用路径压缩，时间复杂度为 $O(m \log n)$。
• 由于路径压缩单次合并可能造成大量修改，有时路径压缩并不适合使用。例如，在可持久化并查集、线段树分治 + 并查集中，一般使用只启发式合并的并查集。

带权并查集

• 我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。

CEOI1999 - Parity Game

• 带权并查集 / 种类并查集。
• 转化为前缀和，每次询问相当于得知 $S[r]$ 和 $S[l - 1]$ 是否是同奇同偶。
• 种类并查集：对于每个位置建立两个点 $i$，$i + n$ 分别代表， 为奇， 为偶。得知两个位置同奇同偶，那么 $i$ 和 $j$ 连，$i + n$ 和 $j + n$ 连，否则 $i$ 和 $j + n$ 连，$j$ 和 $i + n$ 连。一个集合内部的布尔变量相同，当 $i$ 和 $i + n$ 在同一集合时矛盾。
• 带权并查集：相等连一条权值为 $0$ 的边，否则连一条权值为 $1$ 的边，要求两个点的路径异或和要么都为 $1$ （奇偶性不同），要么都为 $0$（奇偶性相同）。实现时维护到达集合代表点的距离即可。

NOI Online #1 提高组 - 序列

• 带权并查集与二分图。
• 把每个位置看成一个点。
• 首先对于 $2$ 操作连边。每次操作可以在一个连通块内部任选一个点加一，任选一个点减一。

• 再对于 $1$ 操作连边。

  • 如果形成的图是二分图，则可以在保证左部点总和与右部点总和的差不变的情况下任意的加减。
  • 如果形成的图不是二分图，则可以在保证总和奇偶性不变的情况下任意的加减。

洛谷 P2391 - 白雪皑皑

• 倒序操作，需要支持将区间没有染色的地方染色。
• 并查集：暴力染色，并删除染过的地方。令 $f[i]$ 从 $i$ 开始第一个没有染色的地方。染色后将 $f[i]$ 设置为 $f[i] + 1$，利用并查集维护。

洛谷 P1640 - [SCOI2010] 连续攻击游戏

• 建图分析。
• 对于每种装备，将其两种属性连边。对于每个连通块来说，如果是一棵树，那么恰好会有一个属性选不到，那么让连通块的最大值选不到。否则至少是个基环树，所有值都可以选到。
• 最终答案就是选不到的属性的最小值。

CF571D - Campus

• 启发式并查集。
• 集合可以想到并查集，但是并查集会破坏合并结构，我们考虑使用启发式合并。
• 如果得到某个位置最后一次清 0 是什么时刻，那么只考虑这个时刻之后的加法操作即可。
• 我们用启发式合并维护信息，第二类集合维护上一次清零的时间，清零就在根结点处打 tag，需要记录连接的时间。
• 然后可以离线下来，变成前缀和相减。
• 加法操作可以记录自己连上来时候父亲的 tag，查询时拿父亲的 tag 减去记录的值即为正确的答案。

最小生成树

洛谷 P1396 - 营救

• 最小生成树思想。
• 将边从小到大排序，然后 Kruskal 最小生成树连边，这样当 $S$ 和 $T$ 第一次联通时，当前边的权值就是答案了。

CF1245D - Shichikuji and Power Grid

• 建图。
• 新建一个虚点，和其相连表示新建电厂，跑最小生成树。

洛谷 P8074 - [COCI2009-2010#7] SVEMIR

• 去除冗边。
• 最小生成树，但代价比较特殊。
• 不妨设两个点的距离由 $x$ 决定，代价为 $\lvert x_A - x_B \rvert$，我们发现在数轴上 $x_A$ 和 $x_B$ 必定是相邻的，否则不如把邻居加进来。
• 所以我们只需 $3n$ 条边，只考虑 $x$，$y$，$z$ 相邻权值连边，跑最小生成树即可。

洛谷 P8207 - [THUPC2022 初赛] 最小公倍树

• 去除冗边。

洛谷 P5994 - [PA2014] Kuglarz

• 思维题。
• 第一步要做前缀和 $S_i$，那么每次询问相当于求 $S_j - S_{i - 1}$ 的奇偶性，我们可以连一条边。
• 也就是求出 $S_j$ 和 $S_{i - 1}$ 的奇偶关系。
• 假设我们得到了最终答案，相当于我们知道了所有 $S_i$ 的奇偶性。而我们知道所有 $S_i$ 的奇偶性后，我们可以通过 $S_i - S_{i - 1}$ 求出第 $i$ 个位置的答案。
• 所以说原问题等价于求出所有 $S_i$ 的奇偶性，因为我们知道 $S_0$ 是偶数，所以就是求最小生成树！

洛谷 P1967 - [NOIP2013 提高组] 货车运输

• 经典题。
• 最优情况下一定是走最大生成树，所以相当于询问最大生成树上两点之间的最小边权，我们用倍增维护即可。

洛谷 P4180 - [BJWC2010] 严格次小生成树

• 次小生成树一定是将某个非树边代替换上的一条边形成的。
• 那么一定代替最大值或严格次大值，倍增记录即可。

CF827D - Best Edge Weight

• 分别考虑树边和非树边。

  • 非树边：只需比环上最大的边小即可，倍增维护即可。
  • 树边：需要小于所有跨过这个树边的非树边中的最小值，倍增打 tag。