NOIP 提高 2012 第一轮 第 22 题：么，图3有

题目

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

答案

5536

题解

考点定位

本题考「树上独立集计数」,对应大纲 4.3.2 动态规划（难度【5】）。

解题过程

树形 DP：每个结点维护「选它 / 不选它」两态的独立集数：

$$f[v][1]=\prod f[c][0],\quad f[v][0]=\prod(f[c][0]+f[c][1])$$

（空集也算独立集。）对图 3 的 15 结点树逐层递推（官方口径）得 5536。

易错提醒

① 「不同的独立集」含空集与单点集——计数按集合内容；② 树形 DP 乘法原理：子树独立决策相乘；选父则子必不选。