整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。

难度为阅读建议，可从 ACM 学习索引 按阶段阅读。

对于种类并查集主要是考虑清楚到根节点距离分为几类，每一类的意义

有的题目相出d数组的含义才能想到用带权并查集

1
2
3
4
5
6
7
8
9
10
11
//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];
}

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

1
2
3
4
5
6
7
8
9
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];//不能颠倒顺序，先维护距离再移动根
}