题意：初始有N个集合，分别为 1 ，2 ，3 .....n。有三种操件

1 p q 合并元素p和q的集合

2 p q 把p元素移到q集合中

3 p 输出p元素集合的个数及全部元素的和。

 

题解：

并查集。只是并查集中并没有删除的操作。所以就需要将删除的这个点的影响降到0，也就是给删除的点申请一个新的id，以后都是用这个新的id来表示这个点，这样原来的那个集合里的点p就没意义，自然影响就为0。

就我写了debug那里比较坑。。

 

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7  8 typedef long long LL; 9 const int N=10*100100;10 int n,m,tot,id[N],fa[N],cnt[N];11 LL sum[N];12 13 int findfa(int x)14 {15     if(fa[x]==x) return x;16     return findfa(fa[x]);17 }18 19 int main()20 {21     freopen("a.in","r",stdin);22     freopen("a.out","w",stdout);23     while(scanf("%d%d",&n,&m)!=EOF)24     {25         for(int i=1;i<=n;i++) id[i]=i,fa[i]=i,cnt[i]=1,sum[i]=i;26         tot=n;27         for(int i=1;i<=m;i++)28         {29             int tmp,x,y,xx,yy;30             scanf("%d",&tmp);31             if(tmp==1)32             {33                 scanf("%d%d",&x,&y);34                 xx=findfa(id[x]);yy=findfa(id[y]);35                 if(xx==yy) continue;//debug36                 fa[xx]=yy;37                 sum[yy]+=sum[xx];38                 cnt[yy]+=cnt[xx];39                 sum[xx]=0;cnt[xx]=0;40             }41             if(tmp==2) 42             {43                 scanf("%d%d",&x,&y);44                 xx=findfa(id[x]);yy=findfa(id[y]);45                 tot++;46                 id[x]=tot;47                 fa[tot]=yy;48                 sum[yy]+=(LL)x;49                 cnt[yy]++;50                 sum[xx]-=(LL)x;51                 cnt[xx]--;52             }53             if(tmp==3)54             {55                 scanf("%d",&x);56                 xx=findfa(id[x]);57                 printf("%d %lld\n",cnt[xx],sum[xx]);58             }59             // for(int j=1;j<=n;j++)60             // {61                 // printf("%d fa = %d cnt = %d sum = %d\n",j,fa[id[j]],cnt[id[j]],sum[id[j]]);62             // }63             // printf("\n");64         }65     }66     67     return 0;68 }