算法思路

题目中一共给了合并和查询和两种操作，很显然我们可以用并查集来实现。但是，查询操作需要给出两个点之间的距离，那么我们怎么去统计这个量呢？

如图，我们可以发现，如果我们想要知道4号点到2号点的距离，如果不压缩路径，我们可以选择一步步去统计这两个点到祖先的距离，然后进行计算。但是，1e5的数据显然是不支持这个时间复杂度的。
那么，我们该怎么做呢？
答案就是用加权并查集。加权并查集和朴素并查集的区别是并查集在统计某节点的父亲节点的同时，还统计该节点到ta的祖先节点的距离。这样，我们就可以进行路径压缩而不是只能一步一步往上跳。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}
const int n = 30000;

int fa[100005],dis[100005],siz[100005],t,x,y;

char s;

int query(int x)
{
    if(fa[fa[x]] == fa[x]) return dis[x];
    return dis[x] + dis[query(fa[x])];
}

int find(int x)
{
    if(fa[x] == x) return x;
//    dis[x] = query(x);
    int ans = find(fa[x]);
    dis[x] = dis[fa[x]] + dis[x];
    fa[x] = ans;
    return ans;
}

int main()
{
    t = read();
    for(int i = 1; i <= n; i ++) fa[i] = i;
    for(int i = 1; i <= n; i ++) siz[i] = 1;
    for(int i = 1; i <= t; i ++)
    {
        cin >> s;
        x = read(); y = read();
        if(s == 'M')
        {
            int fx =  find(x),fy = find(y);
            if(find(x) != find(y))
            {
                dis[fx] = dis[fx] + siz[fy];
                siz[fy] += siz[fx];
                siz[fx] = 0;
                fa[fx] = fy;
            }
        }
        if(s == 'C')
        {
            if(find(x) != find(y))
            {
                printf("-1\n");
                continue;
            }
            if(x == y)
            {
                printf("0\n");
                continue;
            }
            printf("%d\n",abs(dis[x] - dis[y]) - 1);
        }
    }
    return 0;
}