摘要：
开始为您提供n个集合，m个操作，以及初始集合：｛1｝，｛2｝，｝3｝，…，｛n｝有三个操作：1xx1yy1：合并xx1和yy1的两个集合2xx1yy1:分离xx1元素并将其合并为yy1 3xx1：查询xx1集合的元素数量，以及元素的所有值的总和，然后查询集合。1是合并两个集合，3是记录两个权重。因为只需要祖先的权重值，所以“查找”操作不需要更新权重值。下一步是分离元素。这里我使用映射方法：启动每个元素
开始给你n个集合，m种操作，初始集合：{1}, {2}, {3}, … , {n}
操作有三种：
1 xx1 yy1 ： 合并xx1与yy1两个集合
2 xx1 yy1 ：将xx1元素分离出来合到yy1上
3 xx1 ：查询xx1集合的元素个数，和元素所有值总和
并查集，1就是合并两个集合，3要记录两个权值。因为只要祖先的权值，所以Find操作不需要更新权值。
接着就是分离元素了，在这儿我使用映射的方法：开始每个元素都映射自己，接着要删除元素时，我不直接删除元素（因为删除的话可能影响很大），我把此位置映射到不可能出现过得的新的一个值，这样我们处理一下原来的集合，再使用新的值维护一下现在的集合就好了，因为以后我们只是看映射的值，所以虽然没有直接删除值，但是原来的值我们不用。
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=200010; int fat[Max],num[Max]; ll ran[Max]; int mp[Max],tot;//下标映射数字 找新值的代替前面的 void Init(int n) { for(int i=0;i<=n;i++) { fat[i]=i; ran[i]=(ll)i; num[i]=1; mp[i]=i; } tot=n+1; return; } int Find(int x) { if(x==fat[x]) return fat[x]; return fat[x]=Find(fat[x]); } void Union(int x,int y,int typ) { int prex=x;//注意保存原来的值 x=mp[x],y=mp[y];//注意映射 int x1=Find(x); int y1=Find(y); if(x1==y1) return; if(typ==1) { fat[x1]=y1; ran[y1]+=ran[x1]; num[y1]+=num[x1]; return; } mp[prex]=tot++;//删除原有，添加到新地方,注意mp fat[mp[prex]]=y1; num[mp[prex]]=1; ran[mp[prex]]=(ll)x; num[x1]--; ran[x1]-=(ll)prex; num[y1]++; ran[y1]+=(ll)prex; return; } int main() { int n,m; int typ,xx1,yy1; while(~scanf("%d %d",&n,&m)) { Init(n); for(int i=0;i<m;i++) { scanf("%d",&typ); if(typ==1) { scanf("%d %d",&xx1,&yy1); Union(xx1,yy1,1); } else if(typ==2) { scanf("%d %d",&xx1,&yy1); Union(xx1,yy1,2); } else { scanf("%d",&xx1); yy1=Find(mp[xx1]); printf("%d %lld ",num[yy1],ran[yy1]); } } } return 0; }