P16265 [蓝桥杯 2026 省 Python B 组] 蓝小圈 看题，很经典的并查集问题，难点在于当集合合并时怎么做到使原来集合整体操作互不干扰。 这个有很多种办法解决，这里介绍其中一种：按秩合并。 大部分时候我们使用路径压缩的方法优化并查集的合并操作，这样无法保留树的结构。 当我们使用按秩合并时，就可以保留历史的合并操作。这个时候我们只需要在记录并查集整体操作的数组中减去合并过来的那个集合的贡献。计算集合的贡献时就直接从查询的节点向上跳即可。 代码： C++ #include 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>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 `#include 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;in;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: coutget(x)+v[x]"\n"; break; } } return 0; }`
P16265 [蓝桥杯 2026 省 Python B 组] 蓝小圈
笔记