【带权并查集】

带权并查集是结点存有权值的并查集，每个元素的权值通常描述其与并查集中祖先的关系，这种关系如何合并，路径压缩时就如何压缩

与并查集相比，带权并查集可以推算集合内点的关系，而一般并查集只能判断属于某个集合

当两个元素之间的关系可以量化，并且关系可以合并时，可以使用带权并查集来维护元素之间的关系

【合并操作】

带权并查集只是在并查集中加入了一个 value[] 数组，与之相应，在 Union() 函数中也有改变

合并两个元素时，假设 $A$、$B$ 属于不同的树，如果合并这两棵树，把 $A$ 树合并到 $B$ 树上，就需要给 $A$ 树跟他的根结点赋值

假设于 $A$、$B$ 的权值 $Wa$、$Wb$，由于两权值代表的都是与根结点的距离，给根结点所赋的值为：

$$Wa-Wb+x$$

此时，对于原来的结点 $A$，只更新了 $A$ 与其根结点的权值，因此其他结点的更新在查找中实现即可

int father[N];
int value[N];
int Union(int x, int y, int val) {
    int fx = Find(x);
    int fy = Find(y);
 
    if (fx == fy) //如果当前两点与之前距离有冲突
        if(dis[y] != dis[x] + val)
            return 1;
 
    father[fy] = fx;
    value[fy] = value[x] - value[y] + val; //计算两点距离
    return 0;
}

【查找操作】

带权并查集只是在并查集中加入了一个 value[] 数组，与之相应，在 Find() 函数与 Union() 函数中也有改变

int father[N];
int value[N];
int Find (int x) {
    if (father[x] == x)
        return x;
 
    int temp = father[x];
    father[x] = Find(father[x]);
    value[x] += value[temp]; //结点x到根的距离
 
    return father[x];
}

【常见类型】

种类问题

种类统计问题比普通并查集新增一属性，常用于表示它和 father[i] 的关系

例如：用 group[i] 表示和 father[i] 的关系，同类可以用 $0$ 表示，其他两种分别用 $1$ 表示该结点到父结点的单向关系，$2$ 表示该父结点到结点的单向关系

统计问题

统计问题一般是对某种属性进行统计，新增一属性，在路径压缩时执行即可

例如：cnt[x] += cnt[fa]

区间问题

区间问题一般是记录某区间 $[l,r]$ 的数据，此类问题需要对所有值统计设置相同的初值，但初值的大小一般没有影响

对区间 $[l,r]$ 进行记录时，实际上是对势差 $l-1$ 和 $r$ 之间 $(l-1,r]$ 的操作，即：

$$l=l-1$$