10 带权并查集 ★★☆☆☆

带权并查集在普通并查集基础上，给每条「到父亲」的边加一个权值，用来维护集合内元素之间的相对关系

Tips：部分内容由 AI 生成，如发现问题请在评论区留言。

一、基本思想

普通并查集只能判断"是否在同一集合"；带权并查集多维护一个数组 d[]，其中 d[x] 是 x 到其父亲的权值（路径压缩后变成 x 到根的权值）。这样集合内任意两点的相对关系就能用 d 的差表示。

二、核心模板

find：压缩时累加权值

int fa[N], d[N];   // d[x] = x 到父亲的权值int find(int x){    if (fa[x] != x) {        int t = fa[x];       // 先记下原来的父亲        fa[x] = find(t);     // 递归压缩，此时 d[t] 已变成 t 到根        d[x] += d[t];        // x 到根 = x 到父 + 父到根    }    return fa[x];}

merge：带权合并

规定 x 到 y 的权值为 w，即合并后 d[x] - d[y] = w：

void merge(int x, int y, int w){    int fx = find(x), fy = find(y);    if (fx == fy) return;    fa[fx] = fy;    d[fx] = w + d[y] - d[x];}

推导：合并后 x 到新根 fy 的距离是 d[x] + d[fx]，y 到 fy 的距离是 d[y]，要求 (d[x] + d[fx]) - d[y] = w，解出 d[fx] = w + d[y] - d[x]。

查询关系

x、y 的相对权值 = d[x] - d[y]（各自先 find 压缩到根）。

三、例题

1. P2024 [NOI2001] 食物链

题意：三类动物 A、B、C，A 吃 B、B 吃 C、C 吃 A。给 n 个动物、k 句话，每句 1 x y（x、y 同类）或 2 x y（x 吃 y），问有多少句假话。

思路：用 d[x] mod 3 表示 x 与父亲的关系：0 同类、1 吃父亲、2 被父亲吃。合并时同类 w = 0，x 吃 y 时 w = 1。

#include <bits/stdc++.h>using namespace std;const int N = 50005;int fa[N], d[N];int find(int x){    if (fa[x] != x) {        int t = fa[x];        fa[x] = find(t);        d[x] += d[t];    }    return fa[x];}int main(){    ios::sync_with_stdio(false); cin.tie(nullptr);    int n, k; cin >> n >> k;    for (int i = 1; i <= n; i++) fa[i] = i;    int ans = 0;    while (k--) {        int op, x, y; cin >> op >> x >> y;        if (x > n || y > n) { ans++; continue; }        int fx = find(x), fy = find(y);        if (op == 1) {                 // x 与 y 同类            if (fx == fy) {                if ((d[x] - d[y]) % 3) ans++;            } else {                fa[fx] = fy;                d[fx] = d[y] - d[x];   // w = 0            }        } else {                       // x 吃 y            if (fx == fy) {                if ((d[x] - d[y] - 1) % 3) ans++;            } else {                fa[fx] = fy;                d[fx] = d[y] - d[x] + 1;   // w = 1            }        }    }    cout << ans << '\n';    return 0;}

2. P1196 [NOI2002] 银河英雄传说

题意：n 艘战舰，初始第 i 艘在第 i 列。M i j 把 i 所在列整体接到 j 所在列的尾部；C i j 若两舰同列，输出它们之间的战舰数，否则输出 -1。

思路：d[x] 表示 x 前方（到队首/根）的战舰数，sz[x] 表示队列大小。接队尾时 d[fx] = sz[fy]。

#include <bits/stdc++.h>using namespace std;const int N = 30005;int fa[N], d[N], sz[N];int find(int x){    if (fa[x] != x) {        int t = fa[x];        fa[x] = find(t);        d[x] += d[t];    }    return fa[x];}int main(){    ios::sync_with_stdio(false); cin.tie(nullptr);    for (int i = 1; i <= 30000; i++) fa[i] = i, sz[i] = 1;    int T; cin >> T;    while (T--) {        char op; int x, y;        cin >> op >> x >> y;        int fx = find(x), fy = find(y);        if (op == 'M') {            if (fx != fy) {                fa[fx] = fy;                d[fx] = sz[fy];   // 接到队尾，前方有 sz[fy] 艘                sz[fy] += sz[fx];            }        } else {            if (fx != fy) cout << "-1\n";            else cout << abs(d[x] - d[y]) - 1 << '\n';        }    }    return 0;}

四、总结

• • 带权并查集在 fa[] 外加 d[]（到父亲的权值），路径压缩时累加 d[x] += d[老父亲]。
• • 合并公式：d[fx] = w + d[y] - d[x]，其中 w 是 x 到 y 的约定权值。
• • 两点相对关系 = d[x] - d[y]。
• • 应用：维护差值、距离、奇偶性、循环关系等。