「SDOI / SXOI2022」小 N 的独立集 题解

问题分析

核心问题

给定一棵树，每个点的权重在$1 \sim k$中均匀随机，需要统计所有$k^n$种权重分配中，最大权独立集大小为每个可能值$i$（$1 \leq i \leq nk$）的方案数。

关键观察

观察1：经典最大独立集DP

对于固定权重的树，最大权独立集可以用树形DP求解：

• $f[u][0]$：不选节点$u$时，子树的最大独立集和
• $f[u][1]$：选节点$u$时，子树的最大独立集和

转移：

$$f[u][0] = \sum_{v \in son(u)} \max(f[v][0], f[v][1]) $$$$f[u][1] = w_u + \sum_{v \in son(u)} f[v][0]$$

观察2：扩展到计数问题

我们需要统计所有可能的权重分配，因此状态需要记录具体的权重信息。

算法思路

方法一：基于权重和的DP

状态设计： 设$dp[u][s_0][s_1]$表示在节点$u$的子树中：

• 不选$u$时最大独立集和为$s_0$
• 选$u$时最大独立集和为$s_1$ 的方案数。

状态转移： 对于节点$u$，枚举其权重$w$（$1 \leq w \leq k$），然后合并所有子节点的状态。

方法二：优化状态设计

关键洞察：由于$k \leq 5$且$n \leq 1000$，最大独立集和不超过$5000$，但直接记录具体和值状态数仍然太大。

优化思路：记录差值的DP

设$dp[u][d]$表示在节点$u$的子树中，选$u$与不选$u$的最大独立集差值为$d$时的方案数分布。

更具体地，可以设计为： $dp[u][i][j]$：以$u$为根的子树中，最大独立集大小为$i$，且包含某种额外信息的方案数。

算法细节

状态设计优化

由于直接记录具体和值状态数过多，可以采用以下优化：

方案A：记录最大值分布

$dp[u][x]$表示以$u$为根的子树的最大独立集大小为$x$的方案数。

但这样无法处理子节点合并时的复杂情况。

方案B：记录配对状态

$dp[u][a][b]$表示：

• 不选$u$时子树最大独立集为$a$
• 选$u$时子树最大独立集为$b$ 的方案数。

由于$a, b \leq nk = 5000$，状态数$O(n \times nk \times nk)$仍然太大。

方案C：差值DP（官方解法）

设$dp[u][d]$是一个长度为$nk+1$的数组，其中$dp[u][d][s]$表示： 在节点$u$的子树中，选$u$与不选$u$的最大独立集差值为$d$，且最大独立集大小为$s$的方案数。

状态转移

初始化（叶子节点）

对于叶子节点$u$，设其权重为$w$：

• 不选$u$：最大独立集=0
• 选$u$：最大独立集=$w$
• 差值$d = w - 0 = w$

合并子节点

对于节点$u$，设其权重为$w_u$，有子节点$v_1, v_2, ..., v_m$：

1. 不选$u$的情况： 每个子节点可以自由选择是否被选：

   $$s_0 = \sum_{i=1}^m \max(s_{0,v_i}, s_{1,v_i})$$

2. 选$u$的情况： 所有子节点都不能被选：

   $$s_1 = w_u + \sum_{i=1}^m s_{0,v_i}$$

复杂度优化

优化1：状态压缩

由于$k$很小，可以预处理所有可能的权重组合。

优化2：使用生成函数

用多项式表示方案数分布，利用FFT加速卷积。

优化3：阈值剪枝

最大独立集和不会超过实际可能的最大值，可以设置合理的上界。

实现要点

数据结构设计

使用数组或vector存储DP状态，注意内存管理。

合并顺序

按照DFS顺序处理子树，逐步合并状态。

内存优化

由于状态数较多，需要优化存储方式，可能采用滚动数组等技术。

特殊性质利用

$k = 1$的情况

所有点权重均为1，问题简化为经典最大独立集计数。

$k = 2$的情况

权重只有1和2，状态空间相对较小。

小规模数据（$n \leq 8, 30, 100$）

可以使用相对暴力的DP方法。

复杂度分析

最坏情况

• 状态数：$O(n \times nk)$
• 转移复杂度：$O(nk)$
• 总复杂度：$O(n^2k^2)$

对于$n=1000, k=5$，复杂度约$1000^2 \times 25 = 25 \times 10^6$，可以接受。

总结

本题的核心在于将经典的最大权独立集问题扩展到计数版本，关键技巧包括：

1. 状态设计：设计能够记录所有可能权重分配的状态
2. 差值DP：通过记录选与不选的差值来优化状态空间
3. 子树合并：高效合并子节点的状态分布
4. 阈值优化：利用问题限制减少不必要的状态

对于$n \leq 1000, k \leq 5$的数据规模，基于差值DP的解法是可行的，关键在于精细的状态设计和优化。