CC++ & Algorithm

带权并查集

极难2
语言版本：通用
概述：带权并查集在查询和合并时不仅记录集合关系，还维护节点与根之间的权值，用于解决元素间有差值或比例关系的场景。

带权并查集——不仅能“合并”，还能算差值

你有没有遇到过这样的问题：
班上有几个同学，你知道一些同学之间的身高差，比如“小明比小红高5厘米”，“小红比小刚高3厘米”，然后想知道“小明比小刚高多少”？
如果只有一两组关系，手动加一加就行。但如果关系很多，而且时不时有新的关系加入，还可能出现互相矛盾的情况，那我们就需要一个聪明的方法来管理这些信息。

带权并查集就是专门做这个的。它不仅能告诉你两个人是否在同一个“关系网”里（比如他们能否通过一系列已知关系连起来），还能直接算出他们之间的具体差值。

它就像是普通并查集（只记“谁和谁是一伙”）的增强版——每个节点除了记着自己的“老大”（父节点），还记着自己和老大之间的“距离”（比如体重差、身高差、分数差、时间差等）。这样，只要两个节点属于同一个集合，我们就能通过它们到根的距离算出它们之间的差值。

生活中的例子，从简单到复杂

例1：零花钱的秘密

你和三个朋友每个月都会得到零花钱，但具体金额谁也不说。不过，你们互相知道一些比较关系：

  • 你比小华多5元 → 你 - 小华 = 5
  • 小华比小丽多3元 → 小华 - 小丽 = 3
  • 小丽比小刚多2元 → 小丽 - 小刚 = 2

现在你想知道：你比小刚多多少？
很简单：你 - 小刚 = (你 - 小华) + (小华 - 小丽) + (小丽 - 小刚) = 5 + 3 + 2 = 10 元。

但如果是下面这种情况呢：

  • 你比小华多5元
  • 小刚比你多2元（小刚 - 你 = 2）
  • 小华比小刚多1元（小华 - 小刚 = 1）

注意，这里关系“绕了一圈”。手动计算可能会晕，但用带权并查集就能自动处理。

例2：考试分数差值

期末考试后，老师只公布了部分同学的分数差：

  • A比B高10分
  • C比B低4分（即 B - C = 4）
  • A比D高7分

现在问你：C和D谁高，高多少？
用带权并查集，我们可以把每个同学看成一个节点，把分数差看成有向的“距离”，然后轻松算出答案。

核心概念：parent 和 weight

在普通并查集中，我们只有一个 parent 数组，表示每个节点的“父节点”（最终指向根节点）。
在带权并查集中，我们多了一个 weight 数组，其中 weight[x] 表示 节点 x 到它的父节点 parent[x] 的某种差值。方向通常统一为“x 比 parent[x] 大多少”（或者“x - parent[x]”）。具体方向可以根据题目自定义，但一旦定下来，整个程序就要保持一致。

例如：
如果 weight[x] = 3，且 parent[x] = y，那么意味着 x - y = 3，即 x 比 y 重 3 克（或高 3 厘米，多 3 分等）。

关键操作详解

1. find(x)：找到根节点，同时更新权值

find 不仅返回 x 的根节点，还要在路径压缩的过程中，把 x 到**新父节点（即根节点）**的权值计算出来。

步骤：

  • 如果 x 的父节点不是根，先递归找到根的 find(parent[x])。
  • 在递归返回后，parent[x] 已经被指向了根。这时更新 weight[x] += weight[parent[x]]（因为原来的 weight[x] 是 x 到原父节点的差值，而原父节点现在指向了根，weight[parent[x]] 就是原父节点到根的差值，相加就得到了 x 到根的差值）。
  • 最后将 parent[x] 设为根，完成路径压缩。

为什么要这样？
路径压缩后，x 直接指向根，以后查询就会飞快。而权值的累加保证了即使压缩了，x 到根的正确差值依然保留。

2. unite(x, y, value)：合并两个节点，并建立关系

已知 x - y = value（即 x 比 y 重 value）。
我们想要把 x 和 y 所在的集合合并，并设置新权值，使得这个关系成立。

步骤：

  • 找到 x 的根 rx，y 的根 ry。
  • 如果 rx == ry，说明已经在同一集合，此时可以检查之前的关系是否与当前关系冲突（可选）。
  • 否则，将其中一个根（比如 ry）挂到另一个根（rx）下面。我们需要设置 weight[ry]，使得 x - y = value 成立。

推导公式（假设 weight[x] 表示 x 到父节点的差值，方向为 x - parent[x]）：

设：

  • distX = weight[x]（经过 find 后，weight[x] 已经是 x 到 rx 的差值）
  • distY = weight[y]（y 到 ry 的差值）
  • rx 和 ry 是根，它们自身的 weight 为 0（因为 parent 指向自己）。

我们有：

x - y = value
=> (rx + distX) - (ry + distY) = value   // 注意：这里“rx”指的是根节点的值，“distX”是差值，但实际我们用相对值
=> rx - ry = value - distX + distY

现在要将 ry 的父节点设为 rx，需要设置 weight[ry] 使得：

ry - rx = weight[ry]   （根据定义）
=> weight[ry] = ry - rx

由上式 rx - ry = value - distX + distY，所以 ry - rx = -(value - distX + distY) = distX - distY - value。

因此：

weight[ry] = weight[x] - weight[y] - value

注意：不同题目可能有不同定义方向（比如 weight[x] 表示 parent[x] - x），公式的符号会变化。一定要根据自己定义的方向在纸上推导一遍，不要死记硬背。

3. diff(x, y)：查询 x 和 y 的差值

先对 x 和 y 分别调用 find，确保它们到根的权值是最新的。
如果根不同，说明无法确定关系（返回特殊值如 None 或 INF）。
如果根相同，那么：

x - y = (x - root) - (y - root) = weight[x] - weight[y]

4. 冲突检测（可选）

当 unite 时发现 x 和 y 已在同一集合，可以计算根据现有关系应该有的差值 expected = weight[x] - weight[y]，如果这个值与给定的 value 不一致，就说明出现了矛盾。很多题目（如“食物链”）需要检测矛盾。

新手容易犯的错误

❌ 错误1：忘记在 find 中更新权值

很多人写普通并查集的 find 很熟练，一加上权值就忘了累加。结果路径压缩后，weight[x] 还是原来的值，导致后续查询出错。

正确做法：递归返回后，先 weight[x] += weight[parent[x]]，再 parent[x] = root。

❌ 错误2：合并时搞错符号

公式 weight[ry] = weight[x] - weight[y] - value 中的符号很容易搞反。建议每次做题前，用一个小例子手动推导一下。比如：

  • 假设三个节点：0、1、2。
  • 已知 0 - 1 = 5，1 - 2 = 3。合并后查 0 - 2 应为 8。
  • 如果写反了，可能会得到 -8 或别的值。

❌ 错误3：未处理根节点的权值

根节点的 weight 应该是 0（因为 parent[root] = root），千万不要在初始化时随便赋值。初始化为 0 是安全的。

❌ 错误4：类型溢出

差值可能很大（比如几亿），如果用 int 可能溢出。建议用 long long（C++）或 Python 的 int（自动大整数）。

❌ 错误5：忘记路径压缩导致递归过深

虽然带权并查集通常用递归实现 find，但如果数据量很大且没有路径压缩，递归可能很深。路径压缩是必须的，同时也要注意递归栈深度（C++ 中可改为迭代实现）。

完整代码示例（带冲突检测）

下面我们用 C++ 写一个更完整的版本：当发现冲突时输出错误信息。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class WeightedDSU {
private:
    vector<int> parent;
    vector<long long> weight;  // weight[x] = x - parent[x]
public:
    WeightedDSU(int n) {
        parent.resize(n);
        weight.resize(n, 0);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) {
            int root = find(parent[x]);          // 递归找根
            weight[x] += weight[parent[x]];      // 累加权值：现在parent[x]已指向根
            parent[x] = root;                    // 路径压缩
        }
        return parent[x];
    }

    // 合并并返回是否成功（false表示冲突）
    bool unite(int x, int y, long long value) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) {
            // 检查已有关系是否矛盾
            long long expected = weight[x] - weight[y];
            return expected == value;   // 一致则返回true，否则false
        }
        // 将ry的根挂到rx的根下
        parent[ry] = rx;
        weight[ry] = weight[x] - weight[y] - value;
        return true;
    }

    // 查询差值，返回x - y，若不在同一集合返回LLONG_MAX
    long long diff(int x, int y) {
        if (find(x) != find(y)) return LLONG_MAX;
        return weight[x] - weight[y];
    }
};

int main() {
    // 四个砝码：0,1,2,3
    WeightedDSU dsu(4);

    // 输入已知关系，如果出现矛盾就输出
    if (!dsu.unite(0, 1, 2)) cout << "矛盾：0和1的关系与已有关系冲突\n";
    if (!dsu.unite(1, 2, 1)) cout << "矛盾：1和2的关系与已有关系冲突\n";
    if (!dsu.unite(2, 3, 3)) cout << "矛盾：2和3的关系与已有关系冲突\n";

    // 查询0比3重多少
    long long result = dsu.diff(0, 3);
    if (result != LLONG_MAX) {
        cout << "0比3重 " << result << " 克" << endl;   // 输出6
    } else {
        cout << "无法确定0和3的关系" << endl;
    }

    // 测试一个冲突关系：假设有人声称0比2重4克（实际应该是3克）
    if (!dsu.unite(0, 2, 4)) {
        cout << "检测到矛盾：0和2的关系不一致！" << endl;
    }

    return 0;
}

Python 版本（带冲突检测）

class WeightedDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.weight = [0] * n    # weight[x] = x - parent[x]

    def find(self, x):
        if self.parent[x] != x:
            root = self.find(self.parent[x])
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = root
        return self.parent[x]

    def union(self, x, y, value):
        """尝试合并，返回是否成功（False表示矛盾）"""
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            # 检查一致性
            expected = self.weight[x] - self.weight[y]
            return expected == value
        # 将ry的根挂到rx下
        self.parent[ry] = rx
        self.weight[ry] = self.weight[x] - self.weight[y] - value
        return True

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            return None
        return self.weight[x] - self.weight[y]

if __name__ == "__main__":
    dsu = WeightedDSU(4)
    if not dsu.union(0, 1, 2):
        print("矛盾")
    if not dsu.union(1, 2, 1):
        print("矛盾")
    if not dsu.union(2, 3, 3):
        print("矛盾")
    print("0比3重", dsu.diff(0, 3), "克")   # 6

    if not dsu.union(0, 2, 4):   # 应该矛盾，因为实际差3
        print("检测到矛盾：0和2的关系不一致！")

更多应用场景

带权并查集的应用非常广泛，远不止重量差。下面举几个经典例子：

1. 食物链（POJ 1182 / 洛谷 P2024）

三种动物：A吃B，B吃C，C吃A。用带权并查集，其中权值 0 表示与根同类，1 表示吃根，2 表示被根吃（或者反过来）。合并时根据输入的关系（1代表同类，2代表吃）更新权值。

2. 银河英雄传说（NOI 2002）

有 N 艘战舰，分成多个队列。每次命令可以将一整个队列移到另一队列的尾部。需要查询两艘战舰之间的战舰数量。这里权值表示某艘战舰到队首的距离。

3. 区间求和 / 前缀和一致性检查

给你若干条区间和的信息，比如 [l, r] 的和等于某个值。可以将每个下标看成一个节点，权值表示“前缀和之差”。通过带权并查集可以检查这些信息是否矛盾。

4. 带权值的“亲戚关系”

比如已知两个人年龄差（A比B大3岁），可以推断出更多人之间的年龄差。这在家族树或社交网络中很常见。

总结要点（记住这六条）

  1. 定义权值方向要统一：比如 weight[x] = x - parent[x]，所有运算都基于这个定义。
  2. find 中先累加再压缩：递归返回后，先更新权值再改父节点。
  3. 合并公式自己推一遍：不要死记，用纸笔代入小例子验证。
  4. 记得检查冲突：如果题目要求判断是否矛盾，就在 unite 中比较期待值和给定值。
  5. 用 long long：权值可能很大，防止溢出。
  6. 复杂度接近常数：带路径压缩和按秩合并后，每次操作近似 O(α(n))，非常高效。

相关指引

  • 普通并查集：如果你还不熟悉最基础的并查集，建议先学习它的“找朋友”和“合并帮派”功能。
  • 按秩合并：在 unite 时可以选择将较矮的树挂到较高的树上，可以进一步优化。
  • 食物链问题：这是带权并查集的经典题目，强烈建议动手做一遍。
  • 银河英雄传说：另一道经典带权并查集题目，可以练习距离的维护。

带权并查集是并查集的进阶，掌握之后你会发现很多看似复杂的关系问题，都能用它轻松解决。现在，不妨拿一个生活中的关系（比如你和朋友的身高差）来试试编写代码吧！

例题精讲

1单选题

在带权并查集实现中，路径压缩时更新权值的关键操作是什么？已知节点x的父节点为p[x]，dist[x]表示x到父节点的权值，通过递归调用find函数后，p[x]被更新为根节点，此时dist[x]应如何更新？

Adist[x] = dist[x] + dist[p[x]]
Bdist[x] = dist[p[x]] - dist[x]
Cdist[x] = dist[x] + dist[old_parent]
Ddist[x] = dist[p[x]]
2判断题

带权并查集只能处理整数权值，权值必须是整数类型，不能是实数或模意义下的值。

3填空题
下面是带权并查集的find函数（路径压缩时更新权值）。假设dist数组初始化为0，父节点数组为p。请补充空白处的代码。

int find(int x) {
    if (p[x] != x) {
        int root = find(p[x]);
        dist[x] = dist[x] + ___;
        p[x] = root;
    }
    return p[x];
}
4单选题

在带权并查集中，已知节点x到根的距离为dist[x]，节点y到根的距离为dist[y]。现在要合并x和y所在的集合，并且需要满足关系：x到y的权值为d（即value(x,y)=d，且方向为x指向y）。合并操作通常将x的根rx的父节点设为y的根ry，并更新dist[rx]。问dist[rx]应设置为多少？

Adist[y] - dist[x] + d
Bdist[x] - dist[y] + d
Cd - dist[x] + dist[y]
Dd + dist[x] - dist[y]
5填空题
以下为带权并查集的合并操作（按秩合并可选），假设已知关系：x到y的权值为d（x指向y）。请补充空白处的代码。

void unite(int x, int y, int d) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    // 假设按秩合并，以ry为父
    p[rx] = ry;
    dist[rx] = ___;
}