操作を行う際、レベルが低い頂点から操作を行うようにしていいです（レベルが高い頂点は縮約が行われた後もレベルが低い頂点の縮約にはかかわらないため）。

するとまずレベル \(1\) の頂点が存在する場合、レベル \(1\) の頂点からなる誘導部分グラフ（森になります）が完全マッチングを持つことが必要です。さらに、森における完全マッチングは存在する場合一意に定まります。よって縮約操作が一意にさだまるため、レベルが低いものから順に完全マッチングをとって縮約操作を行うようなシミュレーションを行い、実際に \(1\) 頂点からなる木に変換されるかをチェ ックすればいいです。

シミュレーションの際は最小レベルの頂点からなる誘導部分グラフを取得する必要がありますが、毎回 \(T\) の全頂点を走査すると最悪 \(\Theta (N^2)\) 時間かかってしまいます。その代わりに誘導部分グラフにかかわる辺だけを取得するようにしましょう。木 \(T\) の各辺 \(i\) は レベルが \(\min(A_{u_i},A_{v_i})\) である頂点からなる誘導部分グラフを考えるときにはじめて誘導部分グラフに含まれるようになり、以降縮約操作が行われるまでは誘導部分グラフに残り続けます。

これによりレベル \(l\) の頂点 \(2n\) からなる誘導部分グラフは \(O(n)\) 時間で取得できます。 \(2n\) 頂点は縮約操作によって \(n\) 頂点になることから、各頂点の計算量への寄与は \(\sum_{k=0}^{\infty} \frac{1}{2^k} \in O(1)\) であるため、全体で \(O(N)\) 時間でシミュレーションを完了することができます。