【带权并查集】银河英雄

题意：有N艘船，有2种操作， 1、M i j，表示让第 i 号战舰所在列的全部战舰保持原有顺序，接在第 j 号战舰所在列的尾部。

​2、C i j，表示询问第 i 号战舰与第 j 号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

分析：要解决的问题， 1.怎么将i战舰移动到j战舰所在末尾？ 2.i和j号之间有多少战舰？ 解决方法：1.并查集，移动祖先到j战舰的末尾，并更新siz数组,普通并查集为siz[x]+siz[y]+1，本题为siz[x]+nu[y],nu[y]+=nu[x]。意思是x到祖先的路径+=祖先的长度，祖先的长度+=被接上的长度 2.定义siz数组为x到祖先的距离，i到j之间的距离就是 abs ( siz[j]-siz[i] )-1

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+12;
int fa[N],siz[N],m,l,r,son[N],num[N];
char c;
int f(int x)
{
  if( x!=fa[x] )
  {
    int p=f(fa[x]);
    siz[ x ]+=siz[ fa[x] ];
    fa[x]=p;
  }
  return fa[x];
}
int main(){
  for(int i=1;i<=N;i++)
    fa[i]=i,siz[i]=0,num[i]=1;
  cin>>m;
  while(m--)
  {
    cin>>c>>l>>r;
    if( c=='M' )
    {
      int a=f(l),b=f(r);
      siz[a]+=num[b];
      fa[a]=b;
      num[b]+=num[a];
      num[a]=0;
    }
    else
    {
      int a=f(l),b=f(r);
      //cout<<siz[l]<<" "<<siz[r]<<endl;
      if( a!=b ) cout<<-1<<endl;
      else cout<<abs(siz[l]-siz[r])-1<<endl;
    }

  }

}