経路圧縮undoUF、厳しい
uniteの履歴スタックH(history)を持つのは通常のundoUFと同じで
更に非再帰経路圧縮で使うような経路圧縮用スタックDも常設し、圧縮履歴を全部ここに集めたほうが高速だった

root(find)するたびに経路圧縮を行うが、この圧縮過程をDに全部積む
uniteでは現時点のDの長さも記録
rollback(undo)でDのスタックを1個前のunite時まで崩す
計算量はDの出し入れは高々2回ということを考慮すればO(NlogN)時空間になるはず

ただやたら遅いんだよな
334Gみたいな経路圧縮結果が安定しやすいものには使えるかもしれん
経路圧縮の閾値を設定して、あえて圧縮せずにundoの手間を減らす選択もありだけど、どのみち一度は記録用のスタックに積まなきゃいけないからいまいちな気がする
あとは強い人に任せた