CF Garphs

CF746G New Roads

构造题。
显然优先满足强制叶子节点的限制，设第 \(i\) 层叶节点数 \(b_i\) 。考虑到 \(a_i>a_{i+1}\) 则必有第 \(i\) 层 \(b_i\leftarrow a_i-a_{i+1}\) 个点强制为叶子节点，钦定叶子节点后 \(a_i\leftarrow a_i-b_i, k\leftarrow k -\sum{}^{} b_i\) ，显然序列 \(a\) 为单调不降序列。
此时还需钦定 \(k\) 个叶节点，第 \(i\) 层仍有 \(a_i\) 个节点状态待定，我们只需从 \(\sum_{}^{} a_i\) 个待定节点选取 \(k\) 个作为叶节点即可。
时间复杂度 \(\mathcal{O}(n)\)
代码

原文地址：http://www.cnblogs.com/CAL522/p/CF_Graphs_Records.html