Delete and Delete

2 secs 1024 MB

$X$ 回の操作で目的が達成可能かどうかを考えると「根以外の葉を全て削除する」操作を $X$ 回行った後に残っている根以外の頂点が $X$ 個以下であれば達成可能であることがわかります。

頂点を削除する回数は最大でも $N-1$ 回なのでそれぞれの削除を高速に行えれば一連の操作をシミュレーションすることでこの問題に正答できます。

頂点 $i$ の子の個数 $C_i$ と残っている根以外の頂点数 $\mathrm{rem}$ を保持し、以下のように実装するとよいです。

queue（stackでもstd::vectorでもいいです）を用意し、 $C_i=0$ となる $i$ を全て挿入する。また、 $\mathrm{rem}:=N-1$ とする。
$\mathrm{ans} =1,2,\dots$ $ans = 1, 2, \dots$ について昇順に以下の操作を行う。
- queueに含まれる全ての $i$ について、頂点 $i$ を削除して $C_{P_i}:=C_{P_i}-1$ とする。
- $\mathrm{rem} \le \mathrm{ans}$ となった場合は答えとして $\mathrm{ans}$ を出力して終了する。
- 上で $C_{P_i}=0$ となった $P_i$ を記憶しておき、改めてqueueに挿入する。

また、結果としては変わりませんが $X$ について二分探索を行っても構いません。