P16265 [蓝桥杯 2026 省 Python B 组] 蓝小圈

ooliver 发布于 1 天前 40 次阅读 OI

AI 摘要

蓝小圈：当并查集合并时，如何让集合整体操作互不干扰？按秩合并给出答案——保留历史树结构，巧妙减去合并贡献，从此路径压缩不再唯一！

P16265 [蓝桥杯 2026 省 Python B 组] 蓝小圈

看题，很经典的并查集问题，难点在于当集合合并时怎么做到使原来集合整体操作互不干扰。

这个有很多种办法解决，这里介绍其中一种：按秩合并。

大部分时候我们使用路径压缩的方法优化并查集的合并操作，这样无法保留树的结构。

当我们使用按秩合并时，就可以保留历史的合并操作。这个时候我们只需要在记录并查集整体操作的数组中减去合并过来的那个集合的贡献。计算集合的贡献时就直接从查询的节点向上跳即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+5;
int n,q;
int fa[N],sz[N],w[N],v[N];

int find(int x){
    while(x!=fa[x]) x=fa[x];
    return x;
}

int get(int x){
    int res=0;
    while(x!=fa[x]) res+=w[x],x=fa[x];
    res+=w[x];
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
    while(q--){
        int op,x,y;
        cin>>op>>x;
        switch(op){
            case 1:
                cin>>y;
                x=find(x),y=find(y);
                if(x==y) break;
                if(sz[x]>sz[y]) swap(x,y);
                fa[x]=y,sz[y]+=sz[x],w[x]-=w[y];
                break;
            case 2:
                cin>>y;
                v[x]+=y;
                break;
            case 3:
                cin>>y;
                w[find(x)]+=y;
                break;
            case 4:
                cout<<get(x)+v[x]<<"\n";
                break;
        }
    }
    return 0;
}