带权并查集是并查集的一种，每个元素除了知道和什么元素有关，还知道是什么关系。比如 A 和 C 相同，B 和 D 相反，A 和 B 相反，则可以推出 C 和 D 相同。（这好像是种类并查集，不过不影响，种类并查集的题也能用带权并查集所以就不用学种类并查集辽）。

更广义的带权并查集中有这么一个定义，每个元素除了知道和谁有关（祖先是谁）以外，还要存一个和祖先的有向距离 dist。如图。

带权并查集1
带权并查集1

按上面的 A、B、C 的例子，A、C距离为0，B、D 距离为 1。

当我们需要合并 A、B 的时候，如图，除了按照常规的将 A 的祖先 (C) 成为 B 的祖先 (D) 的爸爸，我们还需要重新计算 D 到 C 的距离。

带权并查集2
带权并查集2

显然，
$$ \overrightarrow{DC} = \overrightarrow{AC} + \overrightarrow{BA} - \overrightarrow{BD} $$
即，
$$ D.dist = A.dist + BA - B.dist $$

特别地，当元素关系是 1（相同） 或 0（不同） 的时候，+ 和 - 可以用异或 ^ 代替。

下面是一道 Lutece 上的题。这个题使用的和上面的带权并查集有点不一样当时还没学带权并查集，自己想的，它的距离定义是和当前父亲的距离，而不是和祖先的距离。对于按上面定义的带权并查集，有另外一个 Codeforces 上的题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//Lutece 2153 对答案
//https://acm.uestc.edu.cn/contest/12/problem/K
const int maxn = 10000001;
struct ufset{
    int father;
    int change_with_father; //和当前父亲的距离
}presum[maxn]; //presum[i]:1~i
ufset findrt(int a)
{
    if (presum[a].father == a)
        return { a, 0 };
    else
    {
        ufset rt = findrt(presum[a].father);
        presum[a].father = rt.father;
        presum[a].change_with_father = presum[a].change_with_father xor rt.change_with_father;
        return presum[a];
    }
}
int merge(int a, int b, int c)
{
    int ra = findrt(a).father, rb = findrt(b).father;
    if (ra == rb)
    {
        return (presum[a].change_with_father xor presum[b].change_with_father xor c)xor 1;
    }
    else
    {
        presum[ra].father = rb;
        presum[ra].change_with_father = c^presum[a].change_with_father^presum[b].change_with_father;
        return 1;
    }
}

下面这个就是一个带有离散化的带权并查集的板子。原题是暑期集训时在 Codeforces 上做的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//http://codeforces.com/problemset/problem/1074/D
typedef pair<int, ll> P;
unordered_map<int,P> m; //需要离散化
void init(int cur)
{
    if (m.find(cur) == m.end())
        m[cur] = { cur,0 };
}

int findrt(int cur) //return father
{
    if (m[cur].first == cur)
        return cur;
    else
    {
        int fa = findrt(m[cur].first);
        m[cur].second ^= m[m[cur].first].second;
        m[cur].first = m[fa].first;
        return m[cur].first;
    }
}

void merge(int l, int r, int x)
{
    init(l);
    init(r);
    int rl = findrt(l), rr = findrt(r);
    if (rl == rr)
        return;
    m[rl].first = rr;
    m[rl].second  = m[l-1].second  ^ m[r].second ^ x;
}

int query(int l, int r)
{
    init(l);
    init(r);
    if (findrt(l) == findrt(r))
    {
        return m[l].second ^ m[r].second;
    }
    else
        return -1;
}