[UVa11987]Almost Union-Find

题目大意

题目链接,大意是给你 n 个元素,三种操作,第一种,将两个元素所在的集合并集。第二种,将一个元素并到另一个元素所在的集合里去。第三种查询该元素所在集合的元素个数和权和。

 

做法

普通的并查集是不能删除元素的,因为我们只能知道子节点的父亲是谁,而从来不在乎父节点有什么子节点。
这题的做法并没有真正的删除。而是多维护了一个 change[] 域。这个域用来维护这个节点是否有过从这个集合去另一个集合的。如果有改变过,那我们可以把这个点看成一个虚点,虽然依旧在这个集合的树中,且维持着原来树的关系。但是真正在哪个集合中存在了change[] 域中。
在移动的过程中,要消除当前节点对此集合的影响才能进行移动操作。
num[] 域和 sum[] 域怎么维护就不多说了,具体看代码。
 

代码

 

更新中

One thought on “[UVa11987]Almost Union-Find

  1. Pingback: 并查集 | 火药

发表评论

电子邮件地址不会被公开。 必填项已用*标注