加权并查集是些什么东西啊

P1196

这道题分为两部分考虑，首先考虑两个点是否在一个队列上，这个简单，用并查集就可以了，然而，我们还要考虑的一点是计算两个点的距离，这就怎么处理呢。

嗯，很容易（不）决定用前缀和，我们就会定义一个数组front，其中front[i]表示以i结尾前面的飞船数。这样我们就解决了计算，但是我们怎么维护front呢？

重新看一下结合的过程，假如我们把y列接到了x列上，那么对于x列来说，front不变，对于y列的每个点来说，他们的前面都多了x列的长度个飞船，我们只要加上x列的长度就行

等等？长度？这就意味着我们需要再开一个数组num，其中num[i]表示以i开头的列的长度。嗯，这样就完备了。

不过仔细一看，我们只维护了每个点的祖先，所以我们还要维护它的每一个儿子。维护儿子就放在了find函数的递归里。

--------------------------------------------------