Luogu P8258 [CTS2022] 独立集问题

rizynvu · 2025-07-02 20:33:30 · 题解

cnblogs。

首先能够发现，如果操作了一个点 u，那么能让新的 a_u 是 \sum\limits_{v\in E_u}a_v - a_u，也能是 a_u - \sum\limits_{v\in E_u}a_v。这是因为在操作一次后 v\in E_u 都有 a_v = 0，此时再操作一次 u 就相当于是取反了。

直接考虑过程太难考虑，根据合并贡献的式子可以知道最后的答案一定形如 \sum\limits_{i = 1}^n d_i a_i(a_i \in \{-1, +1\})。

于是尝试判定一个 a 数组能否被得到。
首先如果有一个点 u 满足 \forall v\in E_u, a_u\not = a_v，那么肯定是可以在 u 这里合并一次的，虽然此时并不能确定是否能这样操作，不过可以先进行尝试。
接下来会继续选一个其他的点进行合并，这个点可能会合并上一些还没有合并过的点，但也有可能合并上一个已经合并过的点。

对于还没有合并过的点，肯定要遵循上述的条件：邻域相等，与中心相反，当然如果已经被合并了就不管了。
对于已经合并过的点，也要关心这个点的符号，不过会发现如果符号对得上那可以直接合并，否则可以在这个点刚合并出来的时候就先反转符号。

于是会发现在合并的时候，已合并的点可以自行调整出符号，唯一的限制就是还没有合并过的点需要满足“邻域相等，与中心相反”的条件。

那么就可以发现每次选一个可以合并的点合并，能合并完就是 a 数组合法的充要条件。

于是就有了 \mathcal{O}(2^n n) 的做法，记录 f_{s} 代表 s 二进制下对应的点已经合并过了的贡献最大值，转移就是每次选择一个点 x 并在此合并。

    for (int s = 0; s < (1 << n); s++) {
        for (int x = 0; x < n; x++) {
            f[s | (1 << x) | G[x]] = std::max(f[s | (1 << x) | G[x]], f[s] + std::abs(sum[G[x] & (~ s)] - sum[(1 << x) & (~ s)]));
        }
    }

接下来考虑优化。

刚刚的 dp 其实根本没有用到树的性质，在任意图上都是可行的。

树意味着 u 的贡献只可能给到 u, v(v\in E_u)，那么在定根后，就只需要考虑 u, fa(u), v(v\in son_u) 这些点。

于是考虑设计一个树形 dp：

• 第二维的 0 / 1 代表的是中心符号为正号 / 负号，因为此时 dp 的贡献不只有单个合并，不能直接套用绝对值，但是 |x| = \max(x, -x) 刚好满足我们的需求。
• 需要注意，此时不考虑 fa(u) 的贡献。

在 dp 转移的时候，就需要考虑 u 及其邻域的合并顺序（因为顺序只考虑 u 及其邻域，所以任意一种顺序都可以逆推出至少一种满足限制的合并顺序）。

对于 f_u 的转移：

• 对于 v(v\in son_u)，v 的贡献给到 u, v, w(w\in son_v) 都是合法的。

对于 g_u 的转移：

• 对于 v(v\in son_u)，v 的贡献只能给到 u, w(w\in son_v)。如果 v 的贡献也给到 v，那么 u, v 的顺序无法调配。

对于 h_u 的转移：

• 考虑先枚举 v 代表 v 是 u 及其邻域中操作最早的点。
• 对于 v，v 的贡献只能给到 v, w(w\in son_v)。如果给到 u 会无法调配。
• 对于 v'(v'\in son_u, v'\not = v)，v' 的贡献能给到 u, v', w'(w'\in son_{v'})。

对于 h 的暴力转移是 \mathcal{O}(\sum |E_u|^2) 的，写出转移后容易优化到 \mathcal{O}(n)。