https://www.luogu.com.cn/problem/P1196

想知道并查集每一个连通块的点的数量

想知道每一个点到祖宗节点的距离

#include<iostream>
#include<cmath>
using namespace std;
int f[30001],s[30001],b[30001];//s距离，b点的数量
int find(int o)//查找
{
    if(f[o]==o) return o;
    int k=f[o];
    f[o]=find(f[o]);//路径压缩
    s[o]+=s[k];//更新当前节点到根的距离
    b[o]=b[f[o]];//更新所在集合大小
    return f[o];
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=30000;i++) {f[i]=i;s[i]=0;b[i]=1;}
    for(int i=1;i<=n;i++)
    {
        char ch;
        int x,y,dx,dy;
        cin>>ch>>x>>y;
        if(ch=='M')
        {
            dx=find(x);//查找x的根
            dy=find(y);//查找y的根
            f[dx]=dy;//把x放在y后面
            s[dx]+=b[dy];//更新x的根到新的根的距离
            b[dx]+=b[dy];//更新集合大小
            b[dy]=b[dx];//更新集合大小
        }
        if(ch=='C')
        {
            dx=find(x);
            dy=find(y);
            if(dx!=dy){cout<<-1<<endl;continue;}//不在同一个集合中
            cout<<abs(s[x]-s[y])-1<<endl;//中间战舰的数量等于x到根的距离减y到根的距离减一。
        }
    }
    return 0;
}