light

P9111 [福建省队集训2019] 最大权独立集问题

Problem

给定一棵 \(n\) 个节点的树，并给定每个点的点权 \(a_i\)。

定义一次操作为：

选择一个未被删除的节点 \(u\)，\(w \leftarrow a_u\)，\(\forall v, v \text{ is connected to } u, a_v \leftarrow a_u\)，删除节点 \(u\)。

求所有 \(n!\) 种操作方案中，结果 \(w\) 的最大值。

Solution

首先转化一波题意：把原操作转化为 给边定向，则若一个点 \(u\) 能到达 \(c\) 个点，则它对 \(w\) 的贡献为 \(c\times a_u\)。

然后能想到应该是树形 dp，但这个 dp 设计不是我能想出来的。

记 \(dp_{i, j, k}\) 表示考虑点 \(i\) 的子树内的点的贡献，\(i\) 能到达的点有 \(j\) 个（包括子树外的），其中 \(i\) 能到达其子树内的 \(k\) 个点。

初始值 \(dp_{u, i, 1} = a_u\)（此时还没有考虑 \(u\) 向外的贡献），答案 \(\max(f_{1, i, i})\)。以下 \(v\) 为 \(u\) 的子节点：

\[\begin{aligned} dp_{u, i, j + x} \xleftarrow{\max} dp_{u, i, j} + dp_{v, x, x} + x \times a_u \\ dp_{u, i, j} \xleftarrow{\max} dp_{u, i, j} + dp_{v, i + x, x} \\ dp_{u, i, j} \leftarrow (i - j) \times a_u \end{aligned} \]

第一个转移表示 \(u \to v\)，第二个转移表示 \(v \to u\)，第三个转移是类似 代价提前计算 的思想，即虽然考虑在 \(u\) 的子树内，但当前把 \(u\) 连向外面的贡献也在此时计算了。因为如果你事后再统计贡献，\(u\) 就被压在下面了，并不好处理。注意第三个转移要在把 \(u\) 的所有子节点遍历完后再进行。

该做法为洛谷题解区的做法，时空复杂度均为 \(O(n^3)\)。（时间复杂度的计算形如树形背包）

一道 dp 题调了我很久，根本在于确实是没有完全理解上述 dp 的精髓，而这种 dp 方式也实在是不寻常。我们设计出的 dp 状态中，预先确定了当前点 \(u\) 最终能到达的点的个数，而 dp 转移的实质是在用子树 \(u\) 内的点去填充这些可以到达的点。在当前点 \(u\) 的转移 过程中，\(u\) 的 dp 值是 不完全 的，即没有实时算出连向子树外的贡献，而是在所有子节点 \(v\) 向 \(u\) 转移完后再把 \(u\) 的 dp 值更新正确。或者说，这是一种 阶段性 的 dp 转移。