\(G\) の最小全域木の重みを \(x\), 最大全域木の重みを \(y\) とします。\(x \le K \le y\) であるとき解が存在し、それ以外のとき -1 です。 以下これを示します。

\(x \le K \le y\) を満たさないときに -1 であることは明らかです。

\(x \le K \le y\) を満たすとき、以下のアルゴリズムにより題意を満たす全域木を構築できます。

1. 重み \(0\) の辺だけを残した部分グラフを考え、その連結成分を求める。(ここではまだ重み \(0\) の辺は解に追加しない。)これらの連結成分同士を、閉路を作らないように重み \(1\) の辺で繋ぐ。このとき使う辺の数は \(x\) 本である。
2. 重み \(1\) の辺の本数が \(K\) になるまで、閉路を作らないように重み \(1\) の辺を使う。これは、重み \(1\) の辺のみからなるグラフの森を最大まで拡張すると \(y\) 本の辺を使えるため、\(K \le y\) より可能である。
3. 残りは、閉路を作らないように重み \(0\) の辺を使う。手順 1 により、選んだ重み \(1\) の辺と全ての重み \(0\) の辺を合わせたグラフは連結なので、全域木にすることが可能である。

\(x,y\) を求める部分ではクラスカル法、全域木構築のアルゴリズムでの連結成分の管理には BFS や Union Find を用いれば良いです。