ユ木を構成する際に，手順2で用意される頂点を 中心，手順3で用意される \(x\) 個の頂点を 1層目 と呼ぶことにします．また，木 \(T\) における頂点 \(v\) の次数を \(d_v\) とします．

中心とする頂点 \(u\) と，1層目の頂点数 \(x\) を固定して考えます．1層目として頂点 \(v_1,v_2,\dots,v_x\) を選んだとすると，\(y\) として選べる最大の値は \(\min\{d_{v_1},d_{v_2},\dots,d_{v_x}\}-1\) です．よって，\(u\) の隣接頂点のうち，次数の上位 \(x\) 個の頂点を選ぶのが最適です．

よって，\(u\) の隣接頂点を次数の降順にソートして \(d_{v_1} \geq d_{v_2} \geq \dots d_{v_{d_u}}\) としておけば，1層目の頂点数 \(x\) を決めたとき，\(v_1,\dots,v_x\) を1層目として選べば，\(y=d_{v_x}-1\) として頂点数 \(1+x+xy\) のユ木を作ることができます．削除する必要のある頂点は \(N-(1+x+xy)\) です．

\(u\) と \(x\) を全探索して，削除する必要のある頂点を計算し，その最小値を求めることで，問題に答えることができます． 時間計算量はソートがボトルネックとなり，\(O(N \log N)\) 時間です．

（ユ木の構成において \(y=0\) を選ぶことはできませんが，\(x=n,y=0\) の「ユ木」は \(x=1,y=n-1\) のユ木とみなせるので，\(y=0\) を除外する必要はありません．）

実装例 (Python)