Halving implementation of UnionFind and root should be the node with
None parent