UVa 1220 Party at Hali-Bula dp：树的最大独立集

UVa 1220 Party at Hali-Bula dp：树的最大独立集

The question is from here.

My Solution

注意点：这个题目有些测试数据是先出现father再出现son的，如

5

jack

jill black

black jack

kar pur

pur black

树的最大独立集问题，扩充到要判定唯一性

状态：d[u][0]表示以u为根的子树中，不选u点能得到的最大人数；f[u][0]为方案唯一性，1为唯一0为不唯一；

相应的有d[u][1],f[u][1]表示选u是的情况

转移：d[u][1]选u则子节点不选，d[u][1] = sum{ d[v][0] | v是u的子节点} 当且仅当f[v][0]全为1是f[u][1]才是1；

          d[u][0]因为u没有选，所以每个子结点v可以选也可以不选，即 d[u][0] = sum{  max(d[v][0], d[v][1]) } 

     如果某个地方d[v][0] == d[v][1] 则不唯一。另外，如果取到最大的那个值为0，则也不唯一；

          对d[0][0]与d[0][1] 输出最大值后，也要最后判断下这2个是否相等；

边界：f[u][1] = f[u][0] = 1;默认当然是要1的

           d[u][0] = 0;当次没选就自己这个结点不算了，

   d[u][1] = 1;

算法：dfs，一层一层下去，直到叶子，然后分别填好 子结构 的 四个状态值；

#include 
#include 
#include 
#include 
#include 

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx