带权并查集

``` #include<bits/stdc++.h> using namespace std; int dis[30001],f[30001],siz[30001]; int t; int find(int x) { if(x==f[x])return x; int temp=f[x]; f[x]=find(f[x]); dis[x]+=dis[temp]; return f[x]; } void merge(int x,int y) { int f1=find(x),f2=find(y); dis[f1]+=siz[f2];; siz[f2]+=siz[f1]; siz[f1]=0; f[f1]=f2; } void init() { for(int i=1;i<=30000;i++)f[i]=i; memset(dis,0,sizeof(dis)); for(int i=1;i<=30000;i++)siz[i]=1; scanf("%d",&t); char ch;int x,y; for(int i=1;i<=t;i++) { scanf("%s%d%d",&ch,&x,&y); if(ch=='M')merge(x,y); else if(ch=='C'){ int f1=find(x),f2=find(y); if(f1!=f2)printf("-1\n"); else { printf("%d\n",abs(dis[x]-dis[y])-1); } } } } int main() { init(); return 0; } ```