带权并查集 统计

带权并查集  统计

例题：hdu Dragon Balls 3635（模板）

与普通并查集不同是新增加两个属性：

cnt[i]：该堆数量

trans[i]：该堆转移次数

操作：

在路径压缩时，trans[x] += trans[fa]。

在合并时，动态更新被合并树的堆数量，并增加合并树的转移次数cnt[fy] += cnt[fx]，trans[fx]++。

 

推荐一篇文章：https://blog.csdn.net/tribleave/article/details/72878239