回の操作で目的が達成可能かどうかを考えると「根以外の葉を全て削除する」操作を 回行った後に残っている根以外の頂点が 個以下であれば達成可能であることがわかります。
頂点を削除する回数は最大でも 回なのでそれぞれの削除を高速に行えれば一連の操作をシミュレーションすることでこの問題に正答できます。
頂点 の子の個数 と残っている根以外の頂点数 を保持し、以下のように実装するとよいです。
- queue（stackでもstd::vectorでもいいです）を用意し、 となる を全て挿入する。また、 とする。
- について昇順に以下の操作を行う。
- queueに含まれる全ての について、頂点 を削除して とする。
- となった場合は答えとして を出力して終了する。
- 上で となった を記憶しておき、改めてqueueに挿入する。
また、結果としては変わりませんが について二分探索を行っても構いません。
余談
当初の間違っていたwriter解を正当にするために設定を捻じ曲げた問題があるのでよければそちらも解いてみてください！