ボールと箱をどちらも Union-Find-Tree のノードだと考えましょう。はじめ \(1 \leq a \leq N\) に対し箱 \(a\) に対応するノードとボール \(a\) に対応するノードがマージされているものとします。

このとき各操作は以下の様に解釈できます。

• 箱 \(X\) に対応するノードと箱 \(Y\)に対応するノードをマージする。その後、箱 \(Y\) に対応するノードを独立させる。
• ボール \(k + 1\) に対応するノードと箱 \(X\) に対応するノードをマージする。
• ボール \(X\) の連結成分内に (必ずただ \(1\) つある) 箱のノードを答える。

クエリに答えるために、通常の Union-Find-Tree で持つ情報に、以下の情報を追加して持ちます。

• その連結成分内に存在する箱のノードはどれか？

箱ノードを独立させる部分は実際には新しいノードを作るのが簡単です。

以上の操作の計算量は全て通常の Union-Find-Tree の計算量と同じです。C++ 実装例