之前一道笔试题考到了这个，现在我拿出来复习一下
0X00 基本解释
之前我们用并查集求的都是两点是不是在一个集合，现在我们要求一个集合的两点之间的距离。
这里的距离不是树上的距离：
看题 https://www.acwing.com/problem/content/240/ 就可以知道，合并两个集合的时候，我们是把一个集合拼在另外一个集合的尾部
所以本质上是一个链表，不过在并查集中我们使用的路径压缩使得，不需要遍历一遍就可以知道长度。
所以在一个集合中求两个点的距离，其实就是两个点到根节点的距离相减。
0X01 代码
https://www.acwing.com/problem/content/240/
from sys import stdin
def readline(n = 2):
if n == 1:
return stdin.readline().replace("\n", "")
return stdin.readline().replace("\n", "").split()
N = 30010
p = [i for i in range(N)]
size = [1 for i in range(N)]
dist = [0] * N
m = int(readline(1))
def find(x):
if p[x] != x:
fa = find(p[x])
# 它到原来根节点的距离 + 原来根节点到现在根节点的距离，路径压缩
dist[x] += dist[p[x]]
p[x] = fa
return p[x]
for i in range(m):
t = readline()
op, x, y = t[0], int(t[1]), int(t[2])
px, py = find(x), find(y)
if op == "M":
if px != py:
# 原来根节点的距离等于合并的另一个集合的大小
dist[py] = size[px]
size[px] += size[py]
p[py] = px
else:
if px != py:
print(-1)
continue
print(max(0, abs(dist[x]-dist[y]) - 1))
