P8779 推导部分和：带权并查集与图论建模详解

P8779 推导部分和，这道题我印象很深。题目标签写着“图论 + 前缀和”，难度“普及+”，但第一次看到题目描述的时候，我根本没想到这题能和图论扯上关系。给你一堆区间和的已知条件，然后问另一个区间和能不能求出来、能求就输出值，听起来像个纯数学推导题，怎么会和并查集有关？直到我把前缀和公式往题干里一代，所有条件都变成了“两个前缀和之差等于某个数”，图论建模的思路一下子就通了。这道题非常适合正在备战蓝桥杯省赛、NOIP普及组或者CSP-J/S的同学去啃，它考察的并不是什么冷门算法，而是把“区间约束”翻译成“图上的边”的能力，这种建模意识在竞赛里比背一百个模板都值钱。

1. 先读懂题目：部分和到底在问什么

1.1 题干里的三个关键要素

先明确题目结构。你有一个长度为 N 的数组，数组元素的值没有直接给出，手里只有 M 条已知信息，每条信息形如“闭区间 [l, r] 的和等于 s”。接下来有 Q 个询问，每个询问也给出一个区间 [l, r]，你要回答：根据已知的 M 条信息，能不能推导出这个区间的和？如果能，输出具体数值；如果不能，输出题目指定的字符串（一般是 UNKNOWN）。

这里要特别注意，题目不会让你还原原数组，只让你求“某个区间和能不能被现有条件唯一确定”。这就意味着你不能尝试把每个元素求出来再去相加，因为已知条件往往只覆盖部分区间，而且区间之间互相重叠、交叉，甚至绕几个弯才能凑出答案。我举个例子：已知 [1,3] 的和是 10，又知道 [4,5] 的和是 7，那 [1,5] 的和当然就是 17，这条询问不需要任何新条件就能算出来。但如果是已知 [1,3] 的和是 10，[2,5] 的和是 2，问你 [1,1] 的和是多少，你就得做减法：[1,1] = [1,3] - [2,3]，而 [2,3] 又能从 [2,5] 和 [4,5] 的关系里推出来。这些关系一环套一环，靠肉眼根本看不过来。

所以这类题的本质不是“线段树维护区间和”，而是“给定若干等式约束，判断两个变量之间的差值能否唯一确定”。想通这一点，整道题的难度就下降了一大半。

1.2 前缀和变换：把区间和改成点对关系

区间和问题里最经典、最朴素的工具就是前缀和。定义前缀和数组 S[i] 表示数组前 i 个元素的和，特别地 S[0] = 0。那么区间 [l, r] 的和可以写成：

S[r] - S[l-1]

这是一个纯粹的代数恒等式，没有任何算法含量，但威力巨大。每一条已知条件“区间 [l, r] 的和是 s”，就等价于“S[r] - S[l-1] = s”。这样一来，题目中所有的区间和条件都被改写成了两个前缀和变量之间的差值等式。

于是问题就完全变形了：现在我们有 N+1 个变量 S[0], S[1], ..., S[N]，已知若干“两个变量之差等于多少”的等式，询问某两个变量 S[l-1] 和 S[r] 的差是否已经被这些等式唯一确定。这个转化是整个题目的题眼，也是“前缀和”三个字出现在题目标签里的原因。后面所有图论建模，全部建立在这个 S 数组之上。

很多同学容易在这里犯一个低级错误：把区间 [l, r] 映射成 S[l] 到 S[r]，写出来的等式是 S[r] - S[l] = s，结果样例都过不了。因为区间 [l, r] 的和包含第 l 个元素，S[l] 是前 l 个元素的和，减掉 S[l] 会丢掉 A[l]，正确做法是减 S[l-1]。这个下标细节我会在第 4 部分展开讲。

2. 图论建模：为什么会想到并查集

2.1 把条件看成带权边

现在我们已经有了若干个等式，比如“S[r] - S[l-1] = s”。在算法竞赛里，遇到这种“两个变量之差恒定”的等式，第一反应就是往图论上靠：把每个前缀和变量看成图上的一个点，把一条等式看成一条有向带权边。

具体来说，对于已知条件 S[r] - S[l-1] = s，我从节点 l-1 向节点 r 连一条权值为 s 的有向边，表示从 l-1 走到 r 时，S 的值增加了 s。当然，等式是对称的，反过来从 r 到 l-1 连一条权值为 -s 的边也完全等价。为了方便统一处理，我们只记录一个方向，但在推导时要注意正负号。

把所有 M 条已知条件都这样转成边之后，图里会出现若干个连通块。比如已知 [1,3] 的和是 10，即在 S[0] 和 S[3] 之间连边；已知 [4,5] 的和是 7，即在 S[3] 和 S[5] 之间连边。那么 S[0]、S[3]、S[5] 就在同一个连通块里，我可以直接推出 S[5] - S[0] = 17，对应区间 [1,5] 的和。

这就是图论视角下“推导”的含义：沿着已知的边，在图上走出一条从起点到终点的路径，把路过边权按方向累加，就得到了两个前缀和变量的差值。

2.2 推导部分和的本质是判断连通性

既然推导的过程就是在图上找路径，那么一个询问 [l, r] 能不能被回答，就等价于问：节点 l-1 和节点 r 在不在同一个连通块里？

如果在同一个连通块里，说明存在一条路径把 S[l-1] 和 S[r] 联系起来，它们的差值可以通过路径上的边权推算出来，答案就是这条路径的总权值。如果不在同一个连通块里，说明没有任何等式把这两个变量关联起来，哪怕拐多少个弯都碰不到一起，那它们的差值就没有任何约束，答案自然就是 UNKNOWN。

这里有个很重要的前提：对于这种“等式型”的关系图，同一个连通块内任意两点之间的差值其实是唯一的。也就是说，不管从 A 走到 B 走的是哪条路，累加出来的权值一定相同。为什么？因为每条边都对应真实存在的前缀和等式，如果存在两条不同的路径推出不同的差值，那就意味着已知条件之间互相矛盾，实际题目数据一般不会这么设计。所以我们只需要关心“通不通”，不需要关心“走哪条路”，这让并查集这种专门维护连通性的数据结构成为最合适的工具。

我习惯用一个生活化的类比来理解它：假设班级里有身高比较记录，“小红比小明高 5 厘米”“小明比小刚高 3 厘米”，那我立刻知道小红比小刚高 8 厘米。但要是小红和小丽之间没有任何一条直接或间接的比较记录，我就永远说不出她俩谁高、高多少。每条身高记录就是一条带权边，小红的“关系连通块”里没有小丽，所以无法推导。区间和问题里，前缀和变量就是这些同学，已知条件就是身高比较记录。

2.3 带权并查集的原理

普通并查集只能回答“两个点是否连通”，而这里还要求“连通时两点之间的差值是多少”，所以要在并查集上额外维护一个权值数组。这个数据结构的通用名字叫“带权并查集”，也叫“关系并查集”。

核心思想很简单：在路径压缩的时候，不光让每个节点直接指向根，还要顺便记录“该节点到根节点的差值”。如果每个节点都知道自己和根节点的相对关系，那么任意两个在同一集合内的节点，就能通过“自己到根的差值”减去“对方到根的差值”来得到两者的差值。

注意这里有个关键选择：d[i] 到底表示“S[i] - S[parent[i]]”还是“S[parent[i]] - S[i]”。不同写法会让合并公式差一个负号，所以一旦选定，后面所有推导都得按同一个约定走。我在这篇题解里统一使用：

d[i] = S[i] - S[parent[i]]

这样路径压缩结束后，d[i] 就是 S[i] - S[root]，查询 S[b] - S[a] 时直接算 d[b] - d[a] 即可，正好是区间和，非常顺手。

3. 代码实现：带权并查集落地

3.1 关键变量与约定

先梳理一下代码里要维护的东西：

• n、m、q：分别表示数组长度、已知条件数量、询问数量。
• parent[x]：x 的父节点，根节点的父节点是自身。
• d[x]：当前约定下，x 到其父节点的权值，即 S[x] - S[parent[x]]；路径压缩后表示 S[x] - S[root]。

初始化的时候，节点编号从 0 到 N，一共 N+1 个点，每个点的父节点都指向自己，d 全部置 0。这一步不要漏掉节点 0，因为区间 [1, r] 的条件会用到 S[0]。

整个算法的复杂度接近 O((M+Q)αN)，α 是反阿克曼函数，实际运行中基本可以看作常数。这意味着即使 M、Q 都到 10^5 甚至 10^6，这个做法都能轻松跑过，不需要担心性能。

3.2 路径压缩与合并公式的推导

先看 find 函数的写法：

int find(int x) { if (parent[x] == x) return x; int root = find(parent[x]); // 先把父节点的根找到 d[x] += d[parent[x]]; // 累加：x到根 = x到旧父 + 旧父到根 return parent[x] = root; // 压缩 }

这里最容易写错的地方是累加的时机。你必须先递归调用 find(parent[x])，把 parent[x] 压缩到根，再去执行 d[x] += d[parent[x]]。因为递归返回后，parent[x] 已经被更新成了根节点，d[parent[x]] 也已经被更新成了“旧父节点到根节点的差值”，这时候累加才是正确的。如果顺序反过来，或者用循环写法时先累加再向上跳，算出来的权值就是错的。

再看合并的公式推导。假设有一条新条件，表示 S[b] - S[a] = w。我分别 find(a) 和 find(b)，得到 a 的根是 ra，b 的根是 rb。

如果 ra == rb，说明 a 和 b 已经在同一个关系连通块里，这条新条件和已有信息要么一致，要么矛盾（可以做矛盾检测，后面扩展部分会讲）。如果 ra != rb，我需要把 ra 所在集合合并到 rb 所在集合，也就是让 parent[ra] = rb。问题来了：d[ra] 应该赋成多少？

此时路径压缩已经完成，所以有：

S[a] = d[a] + S[ra] S[b] = d[b] + S[rb]

把这两个式子代入 S[b] - S[a] = w：

(d[b] + S[rb]) - (d[a] + S[ra]) = w

移项整理：

S[ra] - S[rb] = d[b] - d[a] - w

左边正是 d[ra] 的定义（S[ra] - S[rb]，因为 ra 的父节点要设成 rb）。所以合并操作就是：

void merge(int a, int b, long long w) { int ra = find(a), rb = find(b); if (ra == rb) return; parent[ra] = rb; d[ra] = d[b] - d[a] - w; }

这个公式是整道题最容易抄错的地方。网上一搜能找到好几种写法，有的 d[i] 定义是 S[parent[i]] - S[i]，有的是把 rb 挂到 ra 上，公式都会跟着变。我的建议是你只记住一套，并且每次写代码前都自己从“S[b] - S[a] = w”这个条件手推一遍，熟练之后三十秒就能推完，比硬背公式靠谱得多。

3.3 完整 AC 代码

下面给出我整理的完整代码，加了必要的注释，可以直接在洛谷 P8779 上提交：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n, m, q; int parent[MAXN]; long long d[MAXN]; // 约定：d[x] 表示 S[x] - S[parent[x]] // 路径压缩后，d[x] = S[x] - S[root] int find(int x) { if (parent[x] == x) return x; int root = find(parent[x]); d[x] += d[parent[x]]; // 先递归，后累加，顺序不能反 return parent[x] = root; } void merge(int a, int b, long long w) { // 已知条件：S[b] - S[a] = w int ra = find(a), rb = find(b); if (ra == rb) return; parent[ra] = rb; // 推导：S[ra] - S[rb] = d[b] - d[a] - w d[ra] = d[b] - d[a] - w; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> q; // 节点编号 0..n，一共 n+1 个前缀和变量 for (int i = 0; i <= n; i++) { parent[i] = i; d[i] = 0; } while (m--) { int l, r; long long s; cin >> l >> r >> s; // [l, r] 的和是 s -> S[r] - S[l-1] = s merge(l - 1, r, s); } while (q--) { int l, r; cin >> l >> r; int a = l - 1, b = r; if (find(a) != find(b)) { cout << "UNKNOWN\n"; } else { cout << d[b] - d[a] << "\n"; } } return 0; }

这段代码里有一个很微妙的点：询问时我先执行了 find(a) 和 find(b)，确保两个节点的 d 值都已经是“到根节点的差值”，然后再做 d[b] - d[a]。如果省略掉 find 直接比较 parent，可能会因为路径尚未压缩而取到不全的数据，所以千万不要在查询时偷懒。

4. 一边写题一边踩过的坑

4.1 下标问题：区间左端点要减一

我前面反复强调，区间 [l, r] 对应 S[r] - S[l-1]，所以建边和查询的时候，左端点一律先减 1。这不仅是“减不减”的问题，还直接影响数组开多大。l 的最小值是 1，l-1 最小是 0，所以并查集里存在节点 0，初始化时一定要从 i=0 循环到 i=n，而不是从 1 开始。

我身边有同学第一次做这道题时，把条件映射成了 S[l] 和 S[r]，导致样例能蒙对一部分，一到数据复杂点就全错。排查方法很简单：拿区间 [1,1] 测一下，如果已知 [1,1] 的和是 x，询问 [1,1] 应该直接输出 x。用错误的映射方式，这条就过不去。

4.2 方向与正负号别搞反

带权并查集写久了你会发现，大部分 bug 都是符号问题。这里的根源在于：你读入一条条件 (l, r, s) 后，心里必须立刻锁定一个不可动摇的等式：S[r] - S[l-1] = s。之后无论是合并还是查询，永远从这个等式出发。

如果你在某处突然想“把边反过来连”，或者“把减号换成加号”，那恭喜你，你即将获得一次错两个小时的调试体验。我自己的习惯是：把这道题的数学模型写在草稿纸上，写成大字贴屏幕边，每次写 merge 和查询之前先看一眼，确认公式里的符号一致再动手。

另外提醒一点，题目给的 s 可以是负数，区间和并不一定是正数。所以 d 数组、输入变量都必须是 long long，别为了省事开 int。

4.3 输出字符串的格式别写错

题目要求无法推导时输出指定字符串，我记得是 UNKNOWN，但不同平台、不同年份的题可能大小写或格式略有差异。提交前先看题面里的 Output 部分，确认是“UNKNOWN”“Unknown”还是“unknown”。这种错误不会出现在样例里，只有真正提交才会暴露，很恶心。

4.4 常见问题速查表

我把写这道题时遇到的典型问题整理成一个表，方便你对照排查：

5. 从这道题延伸出去

5.1 另一种写法：建图 + DFS 赋权

带权并查集不是唯一解法。拿到所有条件后，我完全可以先建一张邻接表，然后对这个图做 DFS/BFS，给每个点赋一个“相对权值”。具体做法是：每个连通块内随便选一个点作为基准，把它赋值为 0，然后沿边扩展。如果有一条边表示 S[b] - S[a] = w，而我已经知道 S[a]，就令 S[b] = S[a] + w。如果遇到一个点被重复访问，就检查两次赋的值是否相同，相同则继续，不同则说明条件矛盾。

这种写法的优点是更贴近“图论”直觉，初学者容易理解；缺点是需要把 M 条边全部存下来，而且当条件在线给出时不够灵活。不过对于 P8779 这种离线题目来说，DFS 赋权完全可以 AC。我建议你两种方法都写一遍：用 DFS 帮助自己建立“连通块内相对值唯一”的直观感受，再用带权并查集去体会动态维护的效率。

5.2 向差分约束系统扩展

把题目中的等式 S[r] - S[l-1] = s 改成不等式 S[r] - S[l-1] ≥ s，或者允许同时存在大于等于、小于等于两类约束，问题就会升级成差分约束系统。差分约束的经典解法是把不等式变成带权边，然后求最短路或最长路来判断可行性和求解，它在任务调度、时间窗口规划等问题里应用很广。

P8779 的等式模型是差分约束的一个特例：因为等式是双向的，所有关系都是强约束，所以用并查集就能解决。一旦引入不等式，图里可能出现负环，就要上 SPFA 或者 Bellman-Ford。理解了这道题之后再去学差分约束，你会觉得非常顺滑，因为你已经熟悉了“把代数关系变成图上的边”这一整套思维。

5.3 顺手加上矛盾检测

合并的时候，如果 find(a) == find(b)，说明 a 和 b 已经在同一个集合里，此时它们的差值已经被确定。那么这条新条件给的 w 到底对不对？只需要检查一个等式：

d[b] - d[a] 是否等于 w

如果相等，说明新条件与旧条件一致，什么都没发生；如果不相等，说明已知信息彼此矛盾。这个功能在 P8779 的普通数据里可能用不上，但在很多“判定等式系统是否自洽”的题目里就是核心考点。你可以把 merge 写成返回 bool 的形式，检测到矛盾时返回 false，这样这段代码立刻就能复用到别的题上。

5.4 竞赛策略：这题值不值得死磕

蓝桥杯省赛 A 组这种“普及+”难度的题目，通常是省一和二等奖的分水岭。它不像压轴题那样需要复杂的优化技巧，考察的是你能不能快速建模、准确实现基础数据结构。带权并查集在蓝桥杯、NOIP 提高组、CSP-S 里都是常客，同模型的经典题包括“食物链”“银河英雄传说”“Parity Game”等。我建议的学习路径是：普通并查集 → 带权并查集 → 差分约束。每一步都找两三道真题做透，比盲目刷题有效得多。

最后分享一点个人体会。我第一次独立写这道题时，合并公式推了整整三遍，最后还是因为 d[ra] 的符号问题错了一次。当时很挫败，但后来想明白了：带权并查集这种题，错的从来不是算法框架，而是“我自己定义的符号体系”没有被严格执行。写这类题，先把 d[i] 的含义写死在注释里，把合并公式从等式条件手推一遍再落笔，基本能消灭八成 bug。这道 P8779 虽然只是“普及+”，但它把图论建模、前缀和变换、并查集进阶这三个重要考点串在了一起，吃透它，以后遇到再复杂的部分和问题，你都不会再慌。