Bakser's Blog

我是逗比。

bzoj1060 树上贪心

| Comments

题目描述:给出一棵边权树,询问修改多少边权可使得每个叶子节点到根的距离相等?
贪心的考虑这个问题,最后相等的距离一定是开始距根最远的叶子节点的距离。
递归的思考这个问题,我们是一定要让每个节点的子树中的叶子节点到他的距离相等的,所以我们在搜索回溯过程中记录下离他最远的叶子节点的距离,同时我们通过修改边权来保证其他叶子节点与他的距离相等,当回溯到根节点做了如上操作后,整个问题就解决了。
至于数据出错我就不吐槽了。

Comments

comments powered by Disqus