题解 P8294 [省选联考 2022] 最大权独立集问题

管理员

Solution

根据一些逝去的记忆可以得到一个 DP 状态:(f_{u,x,y}) 表示 (u) 这棵子树,(x) 从子树出去,(y) 进来这棵子树。然后讨论一下状态转移,可以暴力枚举状态,暴力枚举之后发现一件事情,(u,ls,rs) 三个状态中至少一个包含 (u),然后可以想到枚举三条边的执行顺序,这样子状态转移是确定的,可以得到 (6) 种转移。状态优化比较困难。

事实上这种较为基本的 DP 转移讨论状态优化,首先需要把 DP 写成基本形式,也就是刷表法,这种形式的 DP 方程比较易于考虑优化。

首先右儿子为空的情况:

[f_{u,u,i}=min_j(f_{ls,j,i})+d_u+d_i ]
[f_{u,j,i}=f_{ls,j,u}+d_j+d_i ]

然后是左右儿子都非空的情况:

[f_{u,u,i}=min_{j}(f_{ls,j,i}+min_{k}f_{rs,k,j})+d_u+d_i ]
[f_{u,j,i}=f_{ls,j,u}+min_k f_{rs,k,i}+d_j+d_i ]
[f_{u,j,i}=min_{k}(f_{ls,k,u}+f_{rs,j,k})+d_j+d_i ]

对称的转移被省略。

如果仔细观察上述转移形式,可以发现所有的 (f) 值实际上可以被 (mathcal{O}(n^2)) 个状态生成出来,即:

  • (A_{u,i}=f_{u,j,fa_u})
  • (B_{u,i}=minlimits_{j}(f_{ls,j,i}+min_{k}f_{rs,k,j}))
  • (C_{u,i}=min_j f_{u,j,i})
  • (D_{u,i}=min_k(f_{ls,k,u}+f_{rs,i,k}))

做一些工作就可以把 (f) 表示出来,此时我们只要讨论怎么将转移优化到 (mathcal{O}(n^2)) 即可。

精细分析一下,对于 (A) 的求解,显然是对的。对于 (D) 的求解,我们只需要枚举右子树的 (i) 和左子树的 (j) 可以做到 (sum sz_{ls}sz_{rs}) 的复杂度,这个复杂度是 (mathcal{O}(n^2)) 的,只需要讨论 (B,C) 的转移即可,而这两个转移的思路是类似的,以 (C) 为例。

不妨假设 (u) 的左右儿子是全的,将 (f_{u,j,i}) 展开:

[C_{u,i}=min_j(f_{ls,j,u}+C_{rs,i}+d_j+d_i) ]
[C_{u,i}=min_j(D_{u,i}+d_i+d_j) ]

将所有不含 (j) 的项分离除去,发现 (C_{u,i}) 变成了关于 (i) 的函数,可以线性转移。

另外一种方式也是通过精细分析得到状态数量正确。分析我们当前的状态数是 (sum sz_x(n-sz_x)),考虑转化状态,一个直觉是 (y) 这一维并不是很重要,只需要在得到 (y) 的时候直接计算贡献即可,所以可以得到一个这样的状态:(f_{u,x,i}) 表示 (x) 出去,(y) 的贡献为 (i) 的答案。粗略分析可以得到一个 (sum sz_x^2) 的界,看起来不是很优秀,但是发现 (x) 出去,(i) 的贡献不会超过 (x) 的另一边子树,于是可以分析到 (sum sz_{ls}sz_{rs}) 的级别。这是是平方的。

Conclusion

神题,整个过程分析曲折又不失逻辑性,用基础的分析技巧最后得到一个相当困难的问题。分步讨论这题的关键。

  • 状态设计。观察答案的构成形态可以发现,每个点的贡献是它经过的路径长度,考虑路径形态,发现每条边只会被上下经过恰好两次。套路地以子树阶段定义状态,可以发现子树与外界的联系其实相当少,钦定父亲边的贡献构成可以得到一个三方状态。
  • 状态优化。这里用到了一个更为基础也不是很常见的优化方法。首先将状态转移写成填表的基本形式方便分析,然后观察状态实际上可以被更少的状态表示。
  • 转移优化,展开状态式子,优化转移。

其中状态的定义是需要灵感的,后面的过程则较为基础,而基础的部分恰是本题最重要的一部分。本题隐藏在 DP 转移中的性质较为复杂,但关键在于,我们对于状态转移的过程建立了形式直观,也就是使用了恰当的公式刻画它。性质的观察并不只在于直觉与证明,还有建立直观与分析

本题的另一个做法则较为复杂,将状态转化为另一个复杂度形式不同的等价形式,通过精细分析得到正确的复杂度,现在应该学会脱离依赖直觉的分析方式,多动笔去精细分析。