初赛题要手动。。我傻了都。。
设表示以的子树中独立集个数,表示选择节点,表示不选节点。
独立集中的点两两不相邻,所以扩展时不能选两个子节点,扩展时直接左右儿子答案相乘(计数原理)即可。
则得到递推式:,。
按后序遍历编号,求出即可。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题