HDU 6241 Color a Tree

题意：给你一棵树，然后让你对树上的节点进行黑白染色。然后染色有一些要求，对于A类要求，要求在x的子树中，至少有y个节点被染成了黑色；对于B类要求，要求在树的所有节点除了x以及其子树节点外，至少有y个节点被染成了黑色。初始状态树是白色的，现在问你，最少给多少个节点染成黑色之后，能够满足所有的A、B类要求。

思路：二分最后的染成黑色的节点数目，然后判定这个答案是否可行。对于A类要求，相当于直接对节点x设置了一个下界，表示以他为根的子树含有的黑色节点数目的下界。对于B类要求似乎不太好处理。可以进行转化。在非x以及其子树的节点中至少包含y个黑色节点，那么等价于在x以及其子树的节点中至多包含n-y个黑色节点，由此，我们就可以以此为依据确定一个上界。dfs累加每一个儿子节点的上下界，不断缩小上下界。判断在过程中是否有出现上下界不合法的情况，以及我们枚举的答案是否包含在根的上下界之中，来确定当前枚举的答案的正确与否。(注意对于同一个点的要求可能会有多个，不能够使其相互覆盖，而是应该保留特定的要求)

参考博客：https://blog.csdn.net/u013534123/article/details/78523559