238. 银河英雄传说

题目

如果不问两个数之间的距离，那么就是个裸的并查集；

维护距离的话，我们可以像维护树上的节点的距离一样操作；

即维护每个点到根节点的距离，那么两个点之间的距离只需要相减即可(前缀和思想)；

那么如果将a合并到b中，我们最朴素的方法就是像下图这样操作；

但是这样肯定超时，我们优化一下；

a集合中的每个点要走到b节点，必然会经过pa；

那么我们只需要给pa加上一个数，相当于给a集合中的每个元素都加了一个数；

只需要在find函数查找的时候，同时更新距离即可；

注意一个细节；

find函数处理的时候，必须要先处理好父节点，再去处理子节点；

否则dis会少加一些数

#include 

using namespace std;

const int N = 30000 + 10;

int p[N],m,dis[N],sz[N];//dis(i)表示点i到其根节点的距离

void init(){
    for(int i=1;i=0?x:-x;
}
int main(){
    init();
    cin >> m;
    char op;
    int i,j;
    while(m--){
        cin >> op >> i >> j;
        if(op == 'M'){
            merge(i,j);
        }else{
            int fi = _find(i),fj = _find(j);
            if(fi != fj) cout << -1 << 'n';
            //注意fi == fj的情况
            else cout << max(0,-1+_abs(dis[i]-dis[j])) << 'n';
        }
    }
    return 0;
}