如果要在并查集专题里找一道“打通任督二脉”的题我大概率会推荐HDU 3038 How Many Answers Are Wrong。这道题表面上看是个区间和问题系统给你若干条[l, r]区间和为某个值的信息让你统计其中有多少条与前面的信息矛盾。但它的标准做法偏偏落在带权并查集上第一次接触的人很容易懵区间和跟并查集有什么关系等真正把带权并查集弄明白之后你会发现这类“给出一些约束关系统计矛盾”的题目基本上都是同一个套路。这篇文章我打算从零开始拆这道题把它们之间的关系推清楚顺便把代码、坑点、排查经验一次性讲透。适合正在刷并查集进阶题的人也适合刚学完普通并查集、想往深走一步的读者。1. 题目拆解把区间和翻译成前缀和1.1 前缀和才是这道题的“通用语言”先明确题目在说什么。我们有一串长度为 n 的整数但你不知道每个位置具体是多少。系统会给出 m 条信息每条信息形如l r s表示区间[l, r]内所有数的和等于s。问题是这些信息里有多少条和前面已经给出来的信息矛盾如果直接拿区间去比很难判断两条不同区间是不是互相冲突。比如[1,3] 6和[2,4] 7你不是一眼就能看出它们是否矛盾还得看边界处的重叠情况。所以需要换个表达方式。引入前缀和定义设sum[i]表示前 i 个数的和特别地sum[0] 0。那么区间[l, r]的和为s等价于sum[r] - sum[l-1] s这个转化的意义非常大原本区间和是两个位置之间的“差”现在变成两个前缀和变量之间的关系。也就是说每条信息都是在告诉你两个变量之间应该满足什么数值关系。我经常跟朋友开玩笑这是把数组问题改成“账本问题”每个sum[i]就是一笔累计账目信息就是在核对两笔账目相差多少。1.2 为什么不能靠朴素前缀和判断有人会想那我干脆把所有sum[i]都解出来不就行了问题在于输入给出的约束往往是不完整的。比如只有两条信息[1,2]3、[2,3]5你可以推出sum[2]-sum[0]3、sum[3]-sum[1]5但你依然不知道sum[1]具体是几。既然不能确定每个前缀和的具体值也就没法用一套“标准前缀和数组”去逐一验证新信息。换个角度看每来一条信息我们关心的是在已经建立的这些约束关系下这条信息是否和它们相容。这本质上是动态判断“一组变量之间的若干差值约束是否自洽”。并查集天然适合维护这种关系它在回答“两个元素是否属于同一个集合”而带权并查集更进一步能回答“两个元素在同一个集合时它们的值相差多少”。所以这不是偶然的套用而是数据结构跟问题性质正好对上。2. 为什么是带权并查集给并查集加上“距离”2.1 普通并查集复习只关心“认不认识”普通并查集就是维护一堆集合支持find(x)查 x 所在集合的根支持merge(x, y)把两个集合合并。它表达的关系只有“是否在同一个集合里”具体怎么合并、内部结构长什么样一般无所谓。但这道题里我们不光要知道sum[x]和sum[y]是否“被同一个约束网络连起来了”更要知道它们之间具体差多少。普通并查集的信息量不够所以要在边上记录权值。这就是带权并查集每个节点到它的父节点有一条边权表示它们之间的“差值”。2.2 权值的物理意义到根节点的“前缀和偏移量”约定一个表示方式用fa[x]表示 x 的父节点用d[x]表示sum[x] - sum[fa[x]]也就是 x 相对父节点的前缀和偏移。初始时fa[x] x所以d[x] 0。路径压缩做完之后fa[x]会直接指向根节点此时d[x]的含义就升级为d[x] sum[x] - sum[root]这里 root 是 x 所在集合的根。换句话说带权并查集把“同一个集合”解释成“前缀和之间已经建立了确定差值的一组点”。只要两个点在同一个集合里我就能通过它们的d值相减算出它们的前缀和差进而验证区间和是否成立。为什么这个设计合理因为前缀和之间的差值公式是传递的如果我知道sum[a] - sum[b]和sum[b] - sum[c]那自然能推出sum[a] - sum[c]。并查集的树结构恰好帮我们把这种传递关系压缩成了“每个点到根的距离”。2.3 一个小例子先找找感觉设 n 3真实前缀和假设为sum[0]0, sum[1]1, sum[2]3, sum[3]6。第一条信息[2,2]的和为 2也就是sum[2] - sum[1] 2。此时 1 和 2 不在同一个集合合并把 1 挂到 2 下面d[1] -2。这个值正好等于sum[1] - sum[2] 1 - 3 -2。第二条信息[3,3]的和为 3即sum[3] - sum[2] 3。把 2 挂到 3 下面d[2] -3。此时再查find(1)路径压缩会算出来d[1] -5也就是sum[1] - sum[3] -5。看到没树上的边权一直在忠实地表达“前缀和的差”。这跟普通并查集最大的区别就是合并集合时必须根据已知约束把新根节点的权值算准不能乱挂否则后面所有验证都会跟着错。这也正是写代码时最容易出错的地方。3. 两个关键操作的权值推导与实现3.1 查找 find先递归找根再累加权值带权并查集的find和普通版本最大的区别是路径压缩的过程中要同步更新d[x]。递归写法非常直观int find(int x) { if (fa[x] ! x) { int t find(fa[x]); // 先找到根 d[x] d[fa[x]]; // 此时 d[fa[x]] 已经是 fa[x] 到根的偏移 fa[x] t; // 再把父指针直接指向根 } return fa[x]; }这里有一个必须注意的顺序问题一定要先递归、后累加。因为我们要用的是“父节点到根节点的权值”而父节点到根节点的权值只有递归调用返回之后才是最新值。如果写成d[x] d[fa[x]]; find(fa[x]);你累加的可能是父节点更新前的旧权值结果会全错。路径压缩做完之后所有节点的fa都直接指向根d都等于“节点到根的前缀和偏移”。这样一来任意两个同集合节点 x、y 的差就是sum[y] - sum[x] d[y] - d[x]这就是判断区间和是否成立的基准公式。3.2 判断矛盾同一个集合里的简单比较每当读入一条信息l r s先把x l - 1y r代入前缀和公式也就是要检查sum[y] - sum[x] s。先分别find(x)和find(y)。如果它们已经在同一个集合里说明 x 和 y 的前缀和差已经被之前的约束完全确定了直接验证if (d[y] - d[x] ! s) ans;这里要格外小心方向。题目给的是sum[r] - sum[l-1] s所以是y rx l - 1判断时一定是d[y] - d[x]。反过来写成d[x] - d[y]样例可能都过不了因为要么判断条件整体反了要么把答案统计反了。3.3 合并 union跨集合时的权值计算如果find(x)和find(y)返回的根不同说明这两个前缀和之前还没有确定关系需要把两个集合合并。但合并不是随便一挂了事新边权必须满足题目给的约束。设rx find(x)ry find(y)已知d[x] sum[x] - sum[rx] d[y] sum[y] - sum[ry]现在要满足sum[y] - sum[x] s也就是(d[y] sum[ry]) - (d[x] sum[rx]) s整理一下得到sum[rx] - sum[ry] d[y] - d[x] - s如果我们决定把rx挂到ry下面即fa[rx] ry那么新根边权d[rx]的定义是sum[rx] - sum[ry]所以要写fa[rx] ry; d[rx] d[y] - d[x] - s;很多新手在这里推着推着就晕我的经验是动手写代码之前先把这个方程在草稿纸上推一遍。正负号一旦错了后面全盘皆错而且错得相当隐蔽。如果你选择把ry挂到rx下面公式会变成d[ry] d[x] - d[y] s两种写法都行但同一个代码里必须只选一种千万别一会儿挂左边一会儿挂右边。验证一下合并的正确性。回到刚才的例子第一条信息合并 1 和 2x1y2s2。此时 rx1ry2d[1] d[2] - d[1] - s 0 - 0 - 2 -2完全符合预期。再看把 2 挂到 3 下面x2y3s3d[2] 0 - 0 - 3 -3也对。所以这条公式不是背出来的是从“前缀和等式”一步一推得到的。4. 完整 AC 代码与实现细节4.1 初始化别忘了 0 号节点前缀和是从sum[0]开始的所以并查集的下标范围是0到n数组大小必须开n1不要只开到 n。初始化时每个节点的父节点指向自己权值为 0。for (int i 0; i n; i) { fa[i] i; d[i] 0; }如果初始化只从 1 开始第一条信息如果涉及l1那么x0就会找到未初始化的 fa[0]轻则出错重则越界。4.2 读入处理的细节这道题是经典的多组输入要写入while (scanf(%d%d, n, m) ! EOF)。每一组数据开始前都要重新初始化。用scanf是为了避免cin流同步带来的额外开销虽然数据量不大但养成习惯没坏处。读入l r s之后统一转成前缀和下标int x l - 1; int y r;注意这里x不是l是l-1因为区间[l,r]的和要表示成sum[r] - sum[l-1]。这是整个题目最经典的一个坑后面我会单独展开说。4.3 参考代码#include bits/stdc.h using namespace std; const int MAXN 200005; int fa[MAXN]; int d[MAXN]; int find(int x) { if (fa[x] ! x) { int t find(fa[x]); d[x] d[fa[x]]; fa[x] t; } return fa[x]; } int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { for (int i 0; i n; i) { fa[i] i; d[i] 0; } int ans 0; for (int i 0; i m; i) { int l, r, s; scanf(%d%d%d, l, r, s); int x l - 1; int y r; int rx find(x); int ry find(y); if (rx ry) { if (d[y] - d[x] ! s) ans; } else { fa[rx] ry; d[rx] d[y] - d[x] - s; } } printf(%d\n, ans); } return 0; }这份代码结构非常短核心逻辑就两个分支。所有难点都浓缩在了d[rx] d[y] - d[x] - s这一行里。我每次重写这个题都会在提交前盯着这一行再确认一遍公式符号。4.4 关于合并方向的统一说明上面代码统一把rx挂到ry下。因为rx是 x 所在集合的根ry是 y 所在集合的根这样合并之后整棵树的根是ry后面查同集合时d[y] - d[x]的语义保持一致。如果你改成把ry挂到rx下代码就是fa[ry] rx; d[ry] d[x] - d[y] s;两种写法都可以AC但混用就会全乱。所以我的建议是固定一种方向并形成肌肉记忆。我自己习惯“右根挂左根”还是“左根挂右根”其实没那么重要重要的是每次写出d[rx] ...时都知道自己是在给谁赋值、这个值代表谁减谁。5. 实战踩坑与常见问题排查5.1 端点偏移为什么是 l-1 而不是 l这个坑几乎每个初学者都会踩。区间[l, r]的和等于sum[r] - sum[l-1]因为sum[i]是前 i 个元素的和不是以 i 为左端点的和。如果错写成sum[r] - sum[l]左边少算了a[l]这个元素中间信息结果就会错位。我见过有些人用另一种解释把区间映射成“从 l-1 到 r 的一条边”。注意l-1可能等于 0所以数组和初始化都要包含下标 0。注意如果题目输入保证l r那就不用处理顺序问题如果担心数据不合法可以加一句if (l r) swap(l, r);但要注意这改变了区间方向是否匹配题目语义需要看题目描述。大部分在线评测题都会保证输入合法不用画蛇添足。5.2 权值方向搞反导致的隐蔽错误方向反了的典型表现是简单的样例能过复杂的样例答案始终差几。比如把判断条件写成d[x] - d[y] ! s或者合并时写了d[rx] d[x] - d[y] s但后来又用了和它不匹配的判断公式。这种错误用肉眼很难看出来因为代码会“觉得”自己逻辑自洽但数值整体反了。我调试时有个习惯找一组手算数据把每条信息的d值实际推一遍只要有一条对不上就说明方向出问题了。5.3 多组输入忘记初始化HDU 3038 是while循环输入很多人一组数据跑完了直接开始下一组结果fa和d还带着上一组的历史残留。如果上一组合并了很多节点下一组刚开始就可能出现两个本来不该连通的点被错误连通的情况统计结果自然不对。建议把初始化写成一个单独的init()函数每组数据循环开头调用一次。这样逻辑集中不容易漏。5.4 递归深度问题路径压缩之后树的深度通常都很小递归find在n 200000级别下不会爆栈。但如果数据构造比较极端递归层数可能会比较深。想更稳妥的话可以写迭代式find不过带权并查集的迭代版本稍微麻烦一点需要额外记录路径上的节点。我的建议是先用递归写法遇到极端情况再换。对这道题来说递归完全够用。5.5 错误现象速查表错误现象常见原因解决方案样例都过提交 WA多组输入忘了重新初始化每组数据都调用init()答案总是比正确答案小合并方向与判断公式不匹配统一左根挂右根重推公式答案总是比正确答案大端点偏移写成l而不是l-1检查 x 的赋值程序运行异常或越界数组只开到 n没包含 0 号下标数组开n1并从 0 初始化递归超时或爆栈极端链式数据考虑迭代find或按秩合并5.6 调试技巧三组手算数据如果你怀疑自己的代码有问题别急着瞎改构造一组只有两三条信息的样例在纸上把每个节点的d值算出来。比如信息11 2 10合并后d[0]等于多少信息22 3 20合并后d[1]等于多少信息31 3 30这条是否矛盾把这些值跟代码跑出来的中间结果对比很快就能定位是find写错了还是合并公式写错了。我学这个题的时候就是这么干才彻底把正负号弄明白的。6. 一个套路三类变体带权并查集的扩展思路6.1 同余关系从差值到取模带权并查集不只能维护“差值”还可以维护“同余关系”。最经典的例子是“三种动物食物链”那类问题x 和 y 的关系可能是同类、x 吃 y、y 吃 x。你可以把关系编码成 0、1、2 三个状态权值表示“x 到根的相对关系”合并和判断时对 3 取模。代码结构和这个题几乎一模一样只是权值更新从加减变成了模运算。这类题目的特征是信息给出的不是具体数值而是“两者之间的关系类型”而且这种关系可以传递。只要发现“关系可以传递并且能数值化”就可以考虑带权并查集。6.2 距离维护从区间和到序列位移还有一种常见变体是“银河英雄传说”那种问题要求在并查集里维护“每个节点到根的距离”和“集合大小”。合并时不再需要验证信息是否矛盾而是要在查询时输出距离差。这本质上也是带权并查集只不过操作从“判矛盾”变成了“查询值”。做这类题时合并公式的推法和区间和题完全一致先明确要维护的量是什么再用等式表示出来最后决定新根权值。6.3 奇偶性对 2 取模的妙用你还可以把区间和的约束变成“区间内 1 的个数的奇偶性”也就是每条信息告诉你[l, r]的和是奇数还是偶数。用前缀和奇偶性表示就是sum[r] - sum[l-1]模 2 等于 0 或 1。带权并查集完全可以直接处理因为奇偶性就是一种取值只有 0 和 1 的差值关系。这类题比单纯区间和更考验抽象能力因为你要主动把“奇数/偶数”翻译成“模 2 的意义下的数值”。6.4 怎么识别一道题该不该用带权并查集我自己的判断标准有三条信息能否表示成两个变量之间的某种“可传递”的二元关系每次新信息到达时需要和已有信息做“矛盾检测”或“关系查询”关系可以被数值化比如差值、同余类、距离等。满足这三条的题目大概率就是带权并查集的路子。反过来如果问题只是单纯的“两个点是否连通”普通并查集就够了如果要求在线维护复杂图结构可能得用到别的数据结构。总之带权并查集不是凭空来的技巧它就是用来处理“元素之间存在可传递数值约束”的一把标准工具。我个人在做这道题时最大的收获不是背住了这个题的解法和公式而是学会了“先推公式再写代码”。很多人觉得这个题难难不在并查集本身难在合并公式的推导。你只要肯花十分钟在草稿纸上把sum的等式写出来所有符号其实都顺理成章。以后遇到食物链、距离维护、奇偶性这类变体思路也是同一个把约束翻译成权值把矛盾检测翻译成差值比较剩下的交给并查集。最后再分享一个练习建议学完这道题后不妨马上找一道同类型的“关系并查集”题目练手尝试不用看题解自己推出合并公式。能成功推出来才算真正把带权并查集装进了脑子里而不只是记住了某道题的标准答案。