不是VIP会员，不能显示答案

题目解答

题目：
对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图1有5个不同的独立集（1个双点集合，3个单点集合、1个空集），图2有14个不同的独立集。那么图3有________个不同的独立集。
答案：5536
考点： 0
分析：
解答： 这是一道动规题，所以永远不要把初赛想得多么白痴=。=，
1空+5单+6双+2三 ＝14
使用DP求解
设 m(i)为以i号点为根结点 总个数
     f(i)为选i的总个数
     g(i)表示不选i的总个数，显然有
      m(i)=f(i)+g(i)
f(i)=g(left_child[i])*g(right_child[i])
g(i)=m(left_child[i])*m(right_child[i])
m(17)=f(17)+g(17)=1936+3600=5536
f(17)=g(8)*g(8)=44*44=1936
g(17)=m(8)*m(8)=60*60=3600
m(8) =f(8)+g(8)=16+44=60
f(8)=g(1)*g(6)=1*16=16g(8)=m(1)*m(6)=2*22=44
m(6)=f(6)+g(6)=6+16=22
f(6)=g(1)*g(4)=1*6=6g(6)=m(1)*m(4)=2*8=16
m(4)=f(4)+g(4)=2+6=8
f(4)=g(1)*g(2)=1*2=2g(4)=m(1)*m(2)=2*3=6
m(2)=f(2)+g(2)=3
f(2)=g(1)=1g(2)=m(1)=2
m(1)=2f(1)=1g(1)=1
评论：
老师： 0