母题链接：

P1196 [NOI2002] 银河英雄传说

算是提交的第一道 普及+/提高 题。被自己菜到了 awa。

分析

这道题我使用的是带权并查集+路径压缩。这种写法最需要注意的就是处理权值 w
在这道题中,我们的边权值就是这个节点到它的祖先的距离dis。我们期望的一个状态是经过路径压缩后，我们可以在 O(1) 的时间内查询到这个节点的权值。所以怎样处理合并集合时，集合中各个节点的权值。

我们分析题目，发现题目要求的是

第 i 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 j 号战舰所在的战舰队列的尾部。

所以我们分析得出：
- 首先，我们维护 num[i] 数组用于表示 如果 第 i 个节点是一个 祖先（树根） ,那么它拥有的所有的所有 子节点 的个数。
- 对于被合并集合（也就是j所在的集合）的祖先 (公共父节点) 的权值 dis[Set_j] 为 0 + num[Set_i]
- 对于被合并集合的祖先 j ，它的sum[j] 应该为 0

这样，我们就得到了对于每一次路径压缩时的操作思路以及每一次合并时的操作思路

• 在对find（）函数进行路径压缩时，我们不能直接写 return f[x]=find(f[x]) 这样函数就会直接递归，我们就没有办法维护其他数组。我们应该逐层查找，即通过分别查找 f[x] 和 f[f[x]]，然后更新 f[x] 。然后，我们考虑执行完路径压缩后需要维护的数组。

• f1=find(x),f2=find(f1)
  路径压缩 f[x]=f2
  更新距离 dis[inx]+=dis[f1]
  及对于路上的每一个节点，它的新权值 dis 都要加上上一个节点的权值
  这些操作是线性的，自上而下。

• 对于合并 f1=find(i),f2=find(j)
  对于被 merge 的祖先，dis[f2]=sum[f1];
  对于祖先 sum[f1]+=sum[f2]
  对于被合并的祖先 sum[f2]=0 。

AC code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,ina,inb;
char op;
ll a[30010]={0}; 
ll dis[30010]={0};
ll sum[30010]={0};
void init(){
    for(ll i=1;i<=30000;i++){
        a[i]=i;
        sum[i]=1;   
    }
}
ll find(ll inx){
    if(a[inx]==inx)return inx;
    ll f1=a[inx],f2=find(f1);
    a[inx]=f2;
    dis[inx]+=dis[f1];
    return f2;
}
void merge(ll inx,ll iny){
    ll f1=find(inx),f2=find(iny);
    a[f2]=f1;
    dis[f2]=sum[f1];
    sum[f1]+=sum[f2];
    sum[f2]=0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    init();
    while(T--){
        cin>>op;
        if(op=='M'){
            cin>>ina>>inb;//M i -> j
            merge(ina,inb);
        }else{
            cin>>ina>>inb;
            if(find(ina)==find(inb))
            cout<<abs(dis[ina]-dis[inb])-1<<'\n';
            else cout<<-1<<'\n';
        }
    }
    return 0;
}