很明显的 DP 题，\(dp_i\) 表示前 \(i\) 种进行划分的最小用时。
直接转移是 \(O(n^2)\) 的，所以我们需要一些性质。
首先 \(dp\) 数组肯定是单调不减的，那么最后一段的贡献为 \(k\) 时，左端点越往左越好。
这保证了最后一段在种数确定的情况下，左端点也是确定的。
并且很明显最后一段种数上限为 \(\sqrt i\)，否则不如最后一段只有一种。
这样转移就是 \(O(n\sqrt n)\) 了。
我读完题后第一想法是不就是儿子个数最大值吗？然而并不是，有可能还有剩余次数来涂下面几层。
所以我们重点关注的是每棵子树需要多少个上面给自己涂的点。
于是就有： \(dp_i=max(\sum dp_j+son_i-k,0)\)。
\(dp_i\) 表示子树 \(i\) 若 \(i\) 已涂色，那还需要多少个点。
注意到答案具有单调性，那么二分 \(k\) 即可，check 条件只要看 \(dp_1\) 为不为 \(0\) 即可。
标签：sqrt,种数,端点,一段,康复训练,dp From： https://www.cnblogs.com/HEIMOFA/p/18579192