算法学习——带权并查集dls版本

#对于种类并查集主要是考虑清楚到根节点距离分为几类，每一类的意义
#有的题目相出d数组的含义才能想到用带权并查集

//find函数需要变化
int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}

#在查询过程中遇到两个不连通的点，需要合并操作，我们需要注意维护距离

if(find(l)!=find(r)){
//1.a[f[l]]=a[l]-d[l]2.a[f[r]]=a[r]-d[r]
//现在要维护的是d[f[l]];
//最终应该满足3.x=d[f[l]]=a[f[l]]-a[f[r]];
//4.a[j]-a[r]=x;
//将124代入3解得d[f[l]];
d[f[l]]=x-d[l]+d[r];
f[f[l]]=f[r];//不能颠倒顺序，先维护距离再移动根
}