题解:有n个数,m次操作
1:把p的集合并到q集合里面，在同一集合就不用操作
2:把p数字并到q集合里面，在同一集合就不用操作了
3:输出p集合所有在的数字个数和数字总和
题解:：除了操作2其他都是跟普通的带权并查集一样，不过操作2有点不一样如果不在同一个集合，就重新开一个点代表p数字的所对应的点然后并到q里面，并且p原来的集合所对应的数字个数和数字总和减掉该减掉的部分即可
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cctype> using namespace std; const int mx = 2e5+5; int id[mx],p[mx],num[mx],sum[mx]; int n,m,x,y; inline bool read(int &x){ x = 0; char c; c = getchar(); if(c==EOF)return false; while(c<'0'||c>'9') c = getchar(); while(isdigit(c)){ x = x*10+c-'0'; c = getchar(); } return 1; } void init(){ for(int i = 1; i <= n; i++) id[i] = i,p[i] = i,num[i] = 1,sum[i] = i; } int find(int x){ return p[x] == x?x:p[x] = find(p[x]); } void work1(){ read(x),read(y); x = find(id[x]),y = find(id[y]); if(x==y) return ; num[y]+=num[x]; sum[y]+=sum[x]; p[x] = y; } void work2(){ read(x),read(y); if(find(id[x])==find(id[y])) return; int tmp = find(id[x]); sum[tmp]-=x,num[tmp]--; id[x] = ++n; y = find(id[y]); p[n] = y; sum[y]+=x,num[y]++; } void work3(){ read(x); x = find(id[x]); printf("%d %d\n",num[x],sum[x]); } int main(){ while(read(n)&&read(m)){ init(); while(m--){ int casei; read(casei); if(casei == 1) work1(); else if(casei == 2) work2(); else work3(); } } return 0; }
