算法设计思路:
这题有个非常有意思的地方:权值是点x到根节点的距离,每次合并的时候,一棵树合并到另一棵树上时,是那种退化的树(所谓一字长蛇阵),所以每次是队列连接,然后是一个队列的队首接到另一个队列的队尾!所以这个时候我们并不知道节点之间的权重更新的情况,莫非更新一次还要去遍历两个队列??所以我们增加一个数组:cnt[]存储当前元素x作为队首所在的队列的长度!
find:这个不用说,就是:
dis(x, rx) = dis(x, rx) + dis(rx, rx)
由于长度就是那种1、2、3这样子的,所以直接相加
merge:增加一个数组维护队列规模的好处:
假设是px->py
第一步:更新px的状态
dis(px, py) = dis(px, px) + cnt[px] = 0 + cnt[px]
第二步:更新py的队列规模
cnt[py] += cnt[px](把px的队列全部收编!)
第三步:更新px的队列规模
cnt[px] = 0(也可不这么做,反正也用不到了)px不再是队首,归0
AC代码:
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 3e4 + 5;
int t, p[maxn], dis[maxn], cnt[maxn];
int find(int x){
if(x == p[x]) return x;
int r = p[x]; p[x] = find(p[x]);
dis[x] += dis[r];
return p[x];
}
void merge(int x, int y){
int px = find(x), py = find(y);
if(px != py){
p[px] = py;
dis[px] += cnt[py];
cnt[py] += cnt[px];
cnt[px] = 0;
}
}
int main(){
cin >> t;
for(int i = 1;i <= maxn;i++){
p[i] = i;
cnt[i] = 1;
}
while(t--){
char ch; int a, b;
cin >> ch >> a >> b;
if('C' == ch){
if(find(a) == find(b))
cout << abs(dis[a] - dis[b]) - 1 << endl;
else
cout << -1 << endl;
}
else
merge(a, b);
}
return 0;
}