传送门（洛谷）
算法：带权并查集
s
i
z
e
size
size代表当前集合的元素个数
f
a
fa
fa路径压缩后的父亲
d
d
d路径压缩后的
x
x
x到
f
a
[
x
]
fa[x]
fa[x]的路径长度（也就是到父亲的距离）
指令
当收到
M
x
y
\;M \;x \;y\;
Mxy的指令时，合并两个集合，更新所有节点信息当收到
C
x
y
\;C \;x \;y\;
Cxy的指令时，分别找出所属集合，如果是在一个集合则答案为两个距离差值
a
b
s
(
d
[
x
]
−
d
[
y
]
)
−
1
abs(d[x]-d[y])-1
abs(d[x]−d[y])−1（思考容斥）
Code
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define don(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
using namespace std
;
const int maxn
=5e5+10;
const int maxm
=1e3+10;
int n
;
int size
[maxn
],fa
[maxn
],d
[maxn
];
template <class t> inline void read(t
&x
)
{
x
=0;int f
=1;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-') f
=-1;ch
=getchar();}
while(isdigit(ch
)){x
=10*x
+ch
-'0';ch
=getchar();}
x
*=f
;
}
inline int get(int x
) {
if(x
==fa
[x
]) return x
;
int root
=get(fa
[x
]);
d
[x
]+=d
[fa
[x
]];
return fa
[x
]=root
;
}
void readdata() {
read(n
);
rep(i
,1,n
) fa
[i
]=i
,size
[i
]=1;
rep(i
,1,n
) {
char flag
;int x
,y
;
cin
>>flag
>>x
>>y
;
if(flag
=='M') {
int fx
=get(x
),fy
=get(y
);
fa
[fx
]=fy
;
d
[fx
]=size
[fy
];
size
[fy
]+=size
[fx
];
}
if(flag
=='C') {
int fx
=get(x
),fy
=get(y
);
if(fx
==fy
) {
printf("%d\n",abs(d
[x
]-d
[y
])-1);
}
else printf("-1\n");
}
}
}
int main() {
readdata();
return 0;
}
