【题解】
经典的带权并查集题目。
设cnt[i]表示i前面的点的数量，siz[i]表示第i个点(这个点是代表元)所处的联通块的大小；合并的时候更新siz、旧的代表元的cnt，路径压缩的时候维护cnt即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N 30000 7 using namespace std; 8 int n,m,f[N+10],cnt[N+10],siz[N+10]; 9 inline int read(){ 10 int k=0,f=1; char c=getchar(); 11 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 12 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 13 return k*f; 14 } 15 int find(int x){ 16 if(f[x]==x) return x; 17 else{ 18 int fa=find(f[x]); 19 cnt[x]+=cnt[f[x]]; 20 return f[x]=fa; 21 } 22 } 23 int main(){ 24 n=read(); 25 for(rg int i=1;i<=N;i++) f[i]=i,siz[i]=1; 26 for(rg int i=1;i<=n;i++){ 27 char c=getchar(); while(c!='M'&&c!='C') c=getchar(); 28 int x=read(),y=read(); 29 if(c=='M'){ 30 f[x=find(x)]=(y=find(y)); 31 cnt[x]+=siz[y]; 32 siz[y]+=siz[x]; siz[x]=0; 33 } 34 else printf("%d ",find(x)==find(y)?abs(cnt[x]-cnt[y])-1:-1); 35 } 36 return 0; 37 }