又是查并集..没啥好说的...qaq
大概是查并集+、差分思想吧?
d[x]表示我x点到root的距离,然后sz[x]表示x集合的大小.显然root到root的距离为0.我们考虑两个集合合并,显然,我们第一个集合的d[root]设为sz[2].sz[2]的大小又要+sz[1].然后我们第二次查询时,就是原来的d[x]+d[root]了.qwq

#include <bits/stdc++.h>
using namespace std;
const int N=3e4+5;
int sz[N],d[N],fa[N];

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=1;i<=N-5;i++) {sz[i]=1;fa[i]=i;}
    cin>>T;
    while(T--)
    {
        string a;
        int b,c;
        cin>>a>>b>>c;
        int ta=find(b);
        int tb=find(c);
        if(a=="M")//M
        {
            d[ta]=sz[tb];
            sz[tb]+=sz[ta];
            fa[ta]=tb;
        }
        else//C
        {
            if(ta!=tb)    puts("-1");
            else
            {
                if(b==c)    puts("0");
                else        cout<<abs(d[b]-d[c])-1<<endl;
            }
        }
    }
    return 0;
}