\(T\) をグラフ \(G\) の最小全域木とし、適当な根を固定します。

辺 \(e\in T\) に対して、\(T - e\) は \(2\) つの連結成分 \(T_1, T_2\) に分かれます。\(G\) における \(T_1T_2\) 辺全体を \(D_e\) と書くことにします。（なお、このような辺集合は、\(T\), \(e\) に関する基本カットと呼ばれます）

おおよそ次の課題です。

• \(G\) の辺集合が与えられる。これを適切に管理して、次のクエリを実行せよ。
• \(e\in T\) が閉鎖する辺として与えられる。カット \(D_e\) に属する未削除の辺を列挙し、これを辺集合から削除せよ。

カット \(D_e\) は、ある部分木の内外を結ぶ辺全体です。\(T\) の Euler Tour をとれば部分木は区間 \([L,R)\) に対応します。次のような問題になります。

• \(2\) 点集合 \(\{a,b\}\) の集合が与えられる。これを適切に管理して、次のクエリを実行せよ。
• 区間 \([L,R)\) が与えられる。一方のみが \([L,R)\) に属するような未削除の \(2\) 点集合 \(\{a,b\}\) を列挙・削除せよ。

一方のみが \([L,R)\) に属するのは、次のどちらかです。

• 一方が \([L,R)\) 、もう片方が \([0,L)\) に属する
• 一方が \([L,R)\) 、もう片方が \([R,\infty)\) に属する

これは、\(2\) 元集合 \(\{a,b\}\) であって \(L\leq a < R \) を満たすもののうち、\(b\) が最大であるものや最小であるものを取得・削除できるようにしておくことで行えます。セグメント木でできます。

検索・削除は全体で \(O(M)\) 回しか行われないため、例えば償却計算量 \(O(N\log N + M\log M)\) などで解けます。