并查集实际上是由若干棵树构成的森林，我们可以在树中的每条边上记录一个权值，即维护一个数组$d$[ ]，用$d[x]$保存节点x到父节点p[x]之间的边权，每次在路径压缩后，每个访问过的节点都会直接指向树根，如果我们同时更新这些节点的$d$值，就可以利用路径压缩过程来统计每个节点到树根之间的路径上的一些信息。这就是带权并查集。
$Ps:$ 同一个连通块内的点，只要不是第一次加入点中，那么他们就具有同一个父节点，只是到父节点的距离不同。

带权并查集$find():$

int find(int x)
{
    if (x == p[x]) return x;
    int t = find(p[x]);  // 这里是存在对p[x]的先路径压缩，因为如果p[x]还未路径压缩就更新d[x]会错误
    d[x] += d[p[x]]; 
    return p[x] = t;
}
// 也可以这么写:
int find(int x)
{
    if (x == p[x]) return x;
    find(p[x]);
    d[x] += d[p[x]];
    return p[x] = p[p[x]];
}

$int$ $t = find(p[x])$是因为可能$p[x]$合并到集合中的下一步就将$x$合并进来了，$p[x]$还未路径压缩，如果直接$d[x]$+=$d[p[x]]$，$d[x]$加的就是$p[x]$到$p[p[x]]$的距离，并不是到根节点的距离，所以要先$int$ $t = find(p[x])$，让$p[x]$进行路径压缩

1. 利用$d$[ ]对集合内物品进行分类(对$d$[ ]的理解解释例子)

$Acwing.240$ 食物链
$Acwing.239$ 奇偶游戏

2. 利用$d$[ ]完成对不同连通块块内所有点加权值

$Acwing.2069$ 网络分析

因为本题在路径压缩的时候要累加父节点权值作为当前节点的权值，所以当$x$的父节点的父节点就是他自己($p[px]=px$)的时候不需要路径压缩(一般的$find()$里是默认也要进行路径压缩)，不然就会反复累加$x$和$p[x]$之间的边权

3. 差分思想求两个子节点之间的点数

$Acwing.238$ 银河传说