Question

Solution

算是带权并查集一个比较典的题目了

定义 \(d[x]\) 表示战舰 \(x\) 与 \(fa[x]\) 之间边的权值，在路径压缩把 \(x\) 的 \(fa[x]\) 修改为根节点时，把 \(d[x]\) 更新成从 \(x\) 到树根的路径上的所有边权和

然后收到 C x y 的指令时，分别执行 getfa(x) 和 getfa(y) 来查询和路径压缩，如果两个在一个集合中，就返回 \(|d[x]-d[y]|-1\)

考虑合并 M x y 我们把 \(x\) 的祖先 \(fx\) 作为 \(fy\) 的儿子，那么 \(fx\) 到 \(fy\) 的距离就是 \(fy\) 这个集合的大小，所以我们需要另外开一个数组 \(siz[x]\) 记录以 \(x\) 为树根的子树的大小，并在合并时更新

Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline char read_ch(){
	char ch=getchar();
	while(ch!='M'&&ch!='C')ch=getchar();
	return ch;
}
struct dsu{
    int n;
    vector<int> fa,d,siz;
    dsu(int n){
        this->n=n;
        fa.resize(n+1);d.resize(n+1);siz.resize(n+1);
        for(int i=1;i<=n;i++) fa[i]=i,d[i]=0,siz[i]=1;
    }
    int getfa(int x){
        if(fa[x]==x) return x;
        int root=getfa(fa[x]);
        d[x]+=d[fa[x]];
        return fa[x]=root;
    }
    void merge(int x,int y){
        int fx=getfa(x),fy=getfa(y);
        if(fx==fy) return ;
        fa[fx]=fy; // 把 x 的祖先连接到 y 的祖先上面去
        d[fx]=siz[fy];
        siz[fy]+=siz[fx];
    }
    int query(int x,int y){
        int fx=getfa(x),fy=getfa(y);
        if(fx!=fy) return -1;
        return abs(d[x]-d[y])-1;
    }
};

int main(){
    int Q;Q=read();
    dsu d(30000);
    while(Q--){
        char ch=read_ch();
        int x=read(),y=read();
        if(ch=='M') d.merge(x,y);
        else printf("%d\n",d.query(x,y));
    }
    return 0;
}