题解：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)，数据能过。

#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 的语言组织与表述，但算法思路、代码与分析均由作者本人完成。