/ 注册

首页 > 试题广场 > 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如

[填空题]

对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 5 个不同的独立集（1 个双点集合、3 个单点集合、1 个空集），图 2 有 14 个不同的独立集。那么，图 3 有___1______个不同的独立集。

初赛题要手动 $DP$ 。。我傻了都。。

设 $f[i]$ 表示以 $i$ 的子树中独立集个数， $g[i,0]$ 表示选择 $i$ 节点， $g[i,1]$ 表示不选 $i$ 节点。

独立集中的点两两不相邻，所以 $g[i,0]$ 扩展时不能选两个子节点， $g[i,1]$ 扩展时直接左右儿子答案相乘（计数原理）即可。

则得到递推式： $g[i,0]=f[lson[i]]*f[rson[i]]$ ， $g[i,1]=g[lson[i],0]*g[rson[i],0]$ 。

按后序遍历编号，求出 $f[17]$ 即可。

发表于 2019-10-13 22:15:48 回复(0)

问题信息

难度：

1条回答 2收藏 2312浏览

热门推荐