NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 22 题

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

拿到图先别急着数，直接画树形DP状态转移方程：选根时子树只能不选，不选根时子树可选可不选，最后乘起来加和。

学生最容易把独立集定义搞错，以为只要不相邻就行，忘了空集也算一个；或者在计算时漏乘某个子树的状态，导致结果偏小。

这道题考查的是二叉树独立集计数，核心是用树形DP把大问题拆成子问题。独立集的定义很关键：集合里任意两个节点都不能相邻，这意味着如果你选了某个节点，它的所有直接孩子都不能选；反之，如果不选某个节点，它的孩子既可以选也可以不选。树形DP的状态设计就围绕这个逻辑展开：dp[u][0]表示不选节点u时，以u为根的子树能构成的独立集总数；dp[u][1]表示选了节点u时，以u为根的子树能构成的独立集总数。当不选u时，每个孩子v都有两种选择（选或不选），所以dp[u][0]等于所有孩子v的(dp[v][0]+dp[v][1])的乘积；当选了u时，每个孩子v只能不选，所以dp[u][1]等于所有孩子v的dp[v][0]的乘积。最终答案就是根节点的dp[root][0]加上dp[root][1]。命题人挖坑的地方往往在‘空集’这个概念上，图1里明确说了有1个空集，但很多学生容易把它漏掉，导致结果少算1。对于图3这种结构稍复杂的二叉树，直接硬算容易出错，必须严格按状态转移方程一步步推导。从根节点开始，先处理叶子节点：叶子不选时dp[0]=1（只有空集），叶子选了时dp[1]=1（只有单点集），所以叶子节点的总独立集数是2。然后向上递推，把每个节点的两个状态乘起来传给父节点。图3共有5536个不同的独立集，这个结果是通过上述DP过程精确计算得出的，包含了所有可能的组合，包括空集。考频数据来看，树形DP在NOIP提高组初赛中是高频考点，2012年这道题就是典型代表，后续年份虽然没再考过完全相同的题，但这类动态规划思想在树结构上的应用一直是命题热点。未来遇到类似题目，只要抓住‘选与不选’两种状态及其相互制约关系，用乘法原理组合子树结果，就能高效解决。