基本思路
设有一棵以 j 为根的树,设 f[i,j](0<=i<=2,1<=j<=n)表示 j 点的第 i 状态的最小值。
状态:0 ——j 点未被监控,在 j 点放置,控制父结点和子结点。1——j 点未被监控,在 j 点
子结点和子结点的子结点放置,保证子结点中至少有一个被放置,控制 j 点。2——j 点已被
其父结点监控,在 j 点子结点和子结点的子结点放置。
那么 min{f[0,gen],f[1,gen]}即为所求。
转移方程:
观察 i=1 和 i=2 时的式子,由于 i=1 时要保证子结
点中至少有一个被放置以控制 j 点,其它部分两式一样,故 i=1 时的值大于等于 i=2 时的值,
可化简为: