On second thoughts, this really does kind of miss the whole point of Union-Find... but this takes it to its logical conclusion.  The correct way to do it is to use &'a RefCells, that way works pretty easily.  You fundamentally need to use a data structure that is mutable while referenced, since there is nothing stopping a parent from being mutated while a child is pointing to it.