题目描述

维护并查集的次序
考虑如何在合并的时候维护深度。
其实你想一下d[x]的定义就是x到root的距离。那么在什么时候会改变？
1、执行M操作，整体移动，那么a队列的所有战舰都被转移到b的后面。a的d要变
2、对于不是头结点的战舰，在找root的时候要考虑：是否自己原来的root现在d[fa[x]]已经不是0了，不是0就意味着他不是头节点了，那么你就一定要改变了。

//在find函数里的变动
if(fa[x]!=x)
{
    int root=find(fa[x]);
    d[x]+=d[fa[x]];  //关键的一步
    fa[x]=root;
}

//在Merge的时候
fa[pa]=pb;
d[pa]=sz[pb];
sz[pb]+=sz[pa];

#include<bits/stdc++.h>
using namespace std;
int sz[30010],d[30010],fa[30010];
int find(int x)
{
    if(fa[x]!=x)
    {
        int root=find(fa[x]);
        d[x]+=d[fa[x]];
        fa[x]=root;
    }
    return fa[x];
}
int main()
{
    int t;
    for(int i=0;i<30010;i++) d[i]=0,sz[i]=1,fa[i]=i;

    cin>>t;
    while(t--){
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        int pa=find(a),pb=find(b);
        if(op[0]=='M'){
            if(pa!=pb)
            {
                fa[pa]=pb;
                d[pa]=sz[pb];
                sz[pb]+=sz[pa];
            }
        }
        else{
            if(pa!=pb) cout<<-1<<endl;
            else printf("%d\n",max(0,abs(d[a]-d[b])-1));
        }
    }
    return 0;
}