CF1746D题解

很好的一道贪心题。
首先对于每条路径，由于要最大化权值，每条路径肯定要延伸到叶子节点。
切入点肯定在 \(|c_u-c_v|\leq 1\)，也就是说由节点 \(i\) 延伸下去的路径要均匀分配给子节点，比如要从 \(i\) 延伸 \(k\) 条路径下去，肯定每个子节点分配 \(\lfloor \frac{k}{son_u}\rfloor\)（\(son_u\) 是 \(u\) 儿子的数量），这部分可以递归执行。
现在就要解决剩下的 \(k\bmod son_u\) 条路径需要处理，由于只能覆盖一次，把子节点能给父亲的链中选最大的就行了，然后把剩余最大的传给父亲使用，由于每个点最多再被多覆盖一次，这样贪心是一定正确的。
以上操作用堆很容易实现。

原文地址：http://www.cnblogs.com/cooltyl/p/16886192.html