-->
问题:公司有n个人,形成树状结构。除了老板之外,只有一名直接主管。要求尽可能多地选择人员,但不能同时选择一个人和他的直接上级。最多可以选多少人?人,并不是唯一的解决办法。
分析:这道题几乎是最大的树独立集问题,只是多了一个唯一性标准。使用两个数组,一个记录人数,一个判断唯一性。
d[u][0]表示在以u为根的子树中,在不选择u点的情况下可以获得的最大人数,那么d[u][1]表示可以得到的最大人数可以通过选取u点得到。
f[u][0]类似,表示点u在以u为根的子树中是否唯一,那么f[u][1]表示点u是否唯一。
对于d[u][1]的计算,因为选择了u,所以无法选择u的子节点,所以d[u][1] = sum(d[v][0], v为子节点),当 f[v][0] 不唯一时,f[u][1] 也不唯一。
对于d[u][0]的计算,因为u没有被选中,所以它的子节点可以选也可以不选,即选最大的,即d[u][0] = sum( max(d[v][0], d[v][1])), 那么如何判断这个唯一性呢?和上面的差不多了,
还有一个。如果 d[v][0] == d[v][1],那么这不是唯一的。其他的和上面一样。剩下的就简单了,用DFS就可以了。
代码如下:
#包括
#包括
#包括