本問では、Union-Find(DSU)と呼ばれるデータ構造を用いるとグラフに対する「辺の追加」と「\(2\) 頂点が同一連結成分に属しているかの判定」が高速に出来ることを利用します。
まず、\(t_i=1\) なるクエリが存在しない場合、つまりクエリが「辺の削除」と「\(2\) 頂点が同一連結成分に属しているかの判定」の \(2\) 種類からなる場合の解法を考えます。 ここで、Union-Findは「辺の追加」は出来ても「辺の削除」は出来ないので工夫をする必要があります。具体的には、クエリを全て処理し終わった時に残っている辺のみが存在する状態から始めて、クエリを逆順に処理することで「辺の削除」の代わりに「辺の追加」を行いながら「\(2\) 頂点が同一連結成分に属しているかの判定」を達成することが出来ます。
元々の問題、すなわち \(t_i=1\) なるクエリが高々 \(10\) 個存在する場合の解法を考えます。先ほど示したようにクエリを逆順に処理すると、\(t_i=1\) なるクエリにおいて「辺の追加」の代わりに「辺の削除」を行う必要が発生してUnion-Findの機能で対処できなくなります。しかし、\(t_i=1\) なるクエリは高々 \(10\) 個しか存在しないため、これが現れるたびに \(\mathrm{O}(N+M+Q)\) かけてUnion-Findを構築しなおすものとしても十分高速にすべてのクエリに答えることが出来、本問に対して正答することが出来ます。