Delete and Delete 2

頂点 $1$ の子以外を削除対象として選ぶ必要はありません。

頂点 $1$ の子を順に $c_1,c_2,\dots,c_k$ とします。また、$c_i$ の子孫の深さの最大値をそれぞれ $d_i$ とします。 すると問題は以下のように言い換えられます。

言い換えた後の問題について操作回数 $X$ を固定し、$X$ 回の操作で目的が達成可能かを考えます。
結論としては $\displaystyle \sum_{i=1}^{k}\max(d_i-X,0) \le X$ であれば達成可能です。
$X$ について二分探索を行うか $X$ を徐々に増加させながら左辺を管理することで $O(N \log N)$ でこの問題を解くことができます。