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

把“删点顺序”等价成“给每条父子边定向”：早删指向晚删。一个点的原始难度会沿着这些方向，给它能走到的每个点各加一次；所以目标就是挑一套方向，让正权尽量覆盖多点、负权尽量少覆盖。

做法是树形背包。任选

1

为根。对每个点

u

，设状态

f_u(k,i)

：当

u

的整棵子树处理完时，规定“

u

在整棵树最终能到

k

个点、在自己子树能到

i

个点”，此时在

u

子树范围内的最好分数。初始化只有自己那一下。合并一个孩子

v

只有两种方向：若定向

u\to v

，就把

v

子树里取

j

个点并到

i

里，同时多拿

d_u\cdot j

；若定向

v\to u

，

i

不变，但

v

能借

u

的“子树外那一圈”继续扩散，所以用到

v

在“全树可达为

k+j

、子树可达为

j

”的最优值来合并。所有孩子合完，再统一把

u

的难度发到子树外的

(k - i)

个点补进去。根的答案取

\max f_{\mathrm{root}}(i,i)

。

复杂度是

O(n^3)

，空间约

O(n^2)

，数据能过。

CPP

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static void solve() {
    int n;
    cin >> n;
    vector<ll> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    vector<vector<int>> g(n + 1);
    for (int i = 2, x; i <= n; i++) cin >> x, g[x].push_back(i);
    const ll inf = (ll)-4e18;
    struct dp { int sz = 0; vector<vector<ll>> v; };
    function<dp(int)> dfs = [&](int u) -> dp {
        dp tmp;
        tmp.sz = 1;
        tmp.v.assign(n + 1, vector<ll>(2, inf));
        for (int i = 1; i <= n; i++) tmp.v[i][1] = v[u];
        for (int val : g[u]) {
            dp tmp1 = dfs(val);
            vector<vector<ll>> v1(n + 1, vector<ll>(tmp.sz + tmp1.sz + 1, inf));
            vector<ll> arr(n + 1, inf);
            for (int i = 1; i <= n; i++) {
                ll tmp2 = inf;
                int val1 = min(tmp1.sz, n - i);
                for (int j = 1; j <= val1; j++) tmp2 = max(tmp2, tmp1.v[i + j][j]);
                arr[i] = tmp2;
            }
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= tmp.sz && j <= i; j++) {
                    ll tmp2 = tmp.v[i][j];
                    if (tmp2 <= inf / 2) continue;
                    if (arr[i] > inf / 2) {
                        v1[i][j] = max(v1[i][j], tmp2 + arr[i]);
                    }
                    int val1 = min(tmp1.sz, i - j);
                    for (int k = 1; k <= val1; k++) {
                        ll val2 = tmp1.v[k][k];
                        if (val2 <= inf / 2) continue;
                        v1[i][j + k] = max(v1[i][j + k], 
                            tmp2 + val2 + v[u] * (ll)k);
                    }
                }
            tmp.v.swap(v1), tmp.sz += tmp1.sz;
        }
        for (int k = 1; k <= n; k++) for (int i = 1; i <= tmp.sz && i <= k; i++)
                if (tmp.v[k][i] > inf / 2) tmp.v[k][i] += v[u] * (ll)(k - i);
        return tmp;
        };
    dp tmp = dfs(1);
    ll ans = inf;
    for (int i = 1; i <= n; i++) 
        ans = max(ans, tmp.v[i][i]);
    cout << ans << '\n';
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    solve();
    return 0;
}

注

本题解在撰写过程中参考了 ChatGPT 的语言组织与表述，但算法思路、代码与分析均由作者本人完成。

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

文章操作

注

相关推荐

评论

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