【每日一题】4月8日题目精讲 树 贪心

题号 NC13249
名称 黑白树
来源 美团2017年CodeM大赛-初赛B轮
戳我进入往期每日一题汇总贴~
注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐~ 点击查看详情

看到树想一边搜一边处理大概率都是可以的（也有例外，比如昨天那个题就根本和这棵树的样子没什么关系。）首先，我们可以很容易的知道：由于每个点都是向上覆盖的，所以凡是不能被下面的点覆盖上的点都必须要选，而能被子孙节点覆盖的点就一定不选了吗？不一定，反例如图1

叶子节点6一定得选，这个时候5和4都在他的覆盖范围内，如果都不选，3没被覆盖，要选，2要选1要选，一共选了4个点，但是事实上我们选6和5就行了。

（知道了这个贪心策略不对之后我们要去考虑哪里不对，知其然并且知其所以然，了解一个想法为什么错和了解一个想法为什么对是一样的重要，也许你就已经能把这个问题解决了。）

我们还是看上图：当我们按照能覆盖上就不选的方法从下往上选的时候，发现了3没有被下方的点覆盖，我们要做的事情其实是找个点（可能是自己可能是下方的点）覆盖了它，而不仅仅是选择它，在这个例子中显然选择5比选择3更好——这两种选择都能满足覆盖3，但是选择5能到覆盖更上方的点。也就说说，我们真正的策略应该是，当一个点没有被下方已经选了的点覆盖到的时候，我们选择一个它或者它下方的能向上覆盖的最远的点。另外，其实我们也并不关心这个点选的哪个，只需要知道往上能覆盖多远就行了，这个值其实可以直接维护到k数组里面，即我认为由于图中5号点的存在，在dfs返回上方的过程中，我们就可以认为k[4]值是9，k[3]是8（选6来替代选3/4）……

我们用一个f[x]表示在x的子树都被覆盖的当前选择下，最远能往x的上方覆盖多远，f[x] = max(f[son] - 1) ，son是x的儿子。（如果这个点还没选，那么它不会用来更新f的值的，即dfs（4）的时候f[4]是等于0的）

如果一个点所有的儿子都不能向上覆盖到它了，那就在找个点及其子树里面选一个能往上覆盖最远的把它覆盖了，选择的点数+1，且f值被k值更新，如果子树还能覆盖到它，就不用在这里选了（在考虑子树被覆盖的问题的时候就已经选过了。）
代码可戳我查看~

看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目4月15日中午12：00之前写的题解有获得牛币资格~

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴