Luogu P8258 [CTS2022] 独立集问题

首先能够发现，如果操作了一个点

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：

$f_{u, 0 / 1}$ 代表 $u$ 的贡献给到了 $fa(u)$ ， $u$ 的子树内的最大权值。
$g_{u, 0 / 1}$ 代表 $u$ 的贡献给到了 $u$ ， $u$ 的子树内的最大权值。
$h_{u, 0 / 1}$ 代表 $u$ 的贡献给到了 $v(v\in son_u)$ ， $u$ 的子树内的最大权值。
第二维的 $0 / 1$ 代表的是中心符号为正号 / 负号，因为此时 dp 的贡献不只有单个合并，不能直接套用绝对值，但是 $|x| = \max(x, -x)$ 刚好满足我们的需求。
需要注意，此时不考虑 $fa(u)$ 的贡献。

在 dp 转移的时候，就需要考虑

u

及其邻域的合并顺序（因为顺序只考虑

u

及其邻域，所以任意一种顺序都可以逆推出至少一种满足限制的合并顺序）。

对于

f_u

的转移：

$fa(u)$ 一定是 $u$ 及其邻域中操作最早的点。
对于 $v(v\in son_u)$ ， $v$ 的贡献给到 $u, v, w(w\in son_v)$ 都是合法的。

对于

g_u

的转移：

$u$ 一定是 $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)

。

f, g

转移也均为

\mathcal{O}(n)

，最后时间复杂度为

\mathcal{O}(n)

。

代码中注释的就是

h

的暴力转移，第二维为

0

代表邻域为

+1

，为

1

代表邻域为

-1

。

#include <bits/stdc++.h>

using ll = long long;
constexpr ll inf = 1e15;

constexpr int maxn = 351493 + 10;

int n;
ll d[maxn];
std::vector<int> son[maxn];

ll f[maxn][2], g[maxn][2], h[maxn][2];
// f : d[u] -> fa
// g : d[u] -> u
// h : d[u] -> v
// ...[][2] : p / n

void dfs(int u) {
    for (int v : son[u]) dfs(v);
    
    // case 1 : d[u] -> fa

    std::array<ll, 2> s = {};
    for (int v : son[u]) {
        s[0] += std::max({f[v][0], g[v][0], g[v][1], h[v][0], h[v][1]});
        s[1] += std::max({f[v][1], g[v][0], g[v][1], h[v][0], h[v][1]});
    }
    f[u][0] = d[u] + std::max(s[0], s[1]), f[u][1] = -d[u] + std::max(s[0], s[1]);

    // case 2 : d[u] -> u

    s = {};
    for (int v : son[u]) {
        s[0] += std::max({f[v][0], h[v][0], h[v][1]});
        s[1] += std::max({f[v][1], h[v][0], h[v][1]});
    }
    g[u][0] = -d[u] + s[0], g[u][1] = d[u] + s[1];

    // case 3 : d[u] -> v

    h[u][0] = h[u][1] = -inf;
    s = {};
    for (int v : son[u]) {
        s[0] += std::max({f[v][0], g[v][0], g[v][1], h[v][0], h[v][1]});
        s[1] += std::max({f[v][1], g[v][0], g[v][1], h[v][0], h[v][1]});
    }
    for (int v : son[u]) {
        s[0] -= std::max({f[v][0], g[v][0], g[v][1], h[v][0], h[v][1]});
        s[1] -= std::max({f[v][1], g[v][0], g[v][1], h[v][0], h[v][1]});
        const ll valv = std::max(d[u] + std::max(g[v][0], h[v][0]), -d[u] + std::max(g[v][1], h[v][1]));
        h[u][0] = std::max(h[u][0], valv + s[0]), h[u][1] = std::max(h[u][1], valv + s[1]);
        s[0] += std::max({f[v][0], g[v][0], g[v][1], h[v][0], h[v][1]});
        s[1] += std::max({f[v][1], g[v][0], g[v][1], h[v][0], h[v][1]});
    }

    // h[u][0] = h[u][1] = -inf;
    // for (int v : son[u]) {
    //     s = {};
    //     for (int w : son[u]) {
    //         if (w == v) continue;
    //         s[0] += std::max({f[w][0], g[w][0], g[w][1], h[w][0], h[w][1]});
    //         s[1] += std::max({f[w][1], g[w][0], g[w][1], h[w][0], h[w][1]});
    //     }

    //     const ll valv = std::max(d[u] + std::max(g[v][0], h[v][0]), -d[u] + std::max(g[v][1], h[v][1]));
    //     h[u][0] = std::max(h[u][0], valv + s[0]), h[u][1] = std::max(h[u][1], valv + s[1]);
    // }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &d[i]);
    for (int i = 2, x; i <= n; i++) scanf("%d", &x), son[x].push_back(i);

    dfs(1);
    printf("%lld\n", std::max({g[1][0], g[1][1], h[1][0], h[1][1]}));
    return 0;
}

Luogu P8258 [CTS2022] 独立集问题

文章操作

相关推荐

评论

Luogu P8258 [CTS2022] 独立集问题