解説の想定解より計算量は悪化しますが、重心分解による計算量 \(\mathrm{O}(N \log^2 N)\) の解法があります。

\(m\) 頂点の木が与えられたとき、重心を \(c\) として、 \(c\) を含む選び方、ないし木を \(c\) を根とした根付き木とみたとき \(c\) の子であってその部分木内に選ばれる頂点が存在するものが複数ある選び方のみを考えたときの問題を \(\mathrm{O}(m \log m)\) で解く方法を説明します。

木を \(c\) を根とした根付き木とみます。条件を満たすような選び方において \(c\) に向かってくる辺は全て整備されることがわかります。そのため、逆方向の辺のみを考えればよいです。

木 DP の発想で問題の大部分を処理できます。

\(\mathrm{DP}[v][x] :=\) \(v\) の部分木のみを考えて \(x\) 個の頂点を選んだ時の整備される辺コストの合計としてありうる最大値

と定義します。この DP を普通にやると二乗オーダーになりますが、凸性を利用して平衡二分木等で差分を管理すると、いわゆるマージテクにより \(\mathrm{O}(m \log m)\) が達成されます。

実際には、 \(c\) の直接の子のみ、データを全てマージするのではなく、適切に処理して条件を満たす選び方のみを考える必要があります。これは簡単です。

条件を満たさないような選び方は重心分解により再帰的に処理します。ここで、再帰した後の木に含まれない部分の寄与についても適切に求める必要がありますが、これは全て \(\mathrm{O}(m)\) で行うことができます。

以上で \(\mathrm{O}(N \log^2 N)\) が達成できます。適切な実装において十分高速です。