250430 D10 模拟赛 T1 题解

题意

给定一棵以 \(1\) 为根的有根树，每个节点对应一个物品，有两个属性：价值 \(a_i\) 和代价 \(b_i\)。一个物品依赖于它的父节点（根节点除外）。你需要选择一些物品，总代价不能超过 \(m\)，求最大价值和。

\(n,m\le 2000,\ 1\le |a_i|,b_i\le 10^4\)

题解

树上背包只能做到 \(O(n^3)\)（假设 \(n,m,b_i\) 同价）。考虑将问题用 dfn 序拍到序列上。

设 \(f_{i,j}\) 表示考虑了 dfn 序的前 \(i\) 项，钦定选择第 \(i\) 项，总共消耗了 \(j\) 的背包容量，能产生的最大价值。这种状态的 dp 转移量非常大，因为 \(f_{i,j}\) 能贡献到所有 \(i'>i\) 的 \(f_{i'}\)。

考虑减少转移数量。我们可以给转移添加更多约束。然而这种状态似乎没办法添加约束，因为后缀 \([i,n]\) 太自由了。

另一种方法就是重新设计状态，我们将 \(i\) 的转移区域用尽量少的状态覆盖，这样就只需要进行很少的转移了。考虑将后缀的设为状态，记 \(f_{i,j}\) 表示考虑 \([i,n]\) 后缀的所有节点，消耗 \(j\) 的背包容量，能产生的最大价值。

转移顺序也需要改变，我们从后往前 dp。考虑转移，如果当前节点 \(i\) 被选中了，则后缀 \([i+1,n]\) 转换为一个独立的子问题（因为 \([i,n]\) 的节点一定都挂在 \(1\rightarrow i\) 的链下面），因此直接从 \(f_{i+1,j-b_i}+a_i\) 转移。

如果 \(i\) 不选，则 \(i\) 子树内部的任何节点都不能选，其它节点则仍然没有任何（由 \(i\) 产生的）约束。此时我们直接跳过该子树，从 \(f_{i+sz[i],j}\) 转移即可。

时间复杂度 \(O(nm)\)。

代码

#include<iostream>
#include<cstring>
#include<set>
#include<cassert>
using namespace std;
const int N = 2010;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, m;

int a1[N], b1[N], a[N], b[N];
int sz[N], dfn[N], dt;

void dfs(int u, int fa) {
    dfn[u] = ++dt;
    sz[dt] = 1;
    a[dt] = a1[u];
    b[dt] = b1[u];
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == fa) continue;
        dfs(v, u);
        sz[dfn[u]] += sz[dfn[v]];
    }
}

int f[N][N];

// #define FIO

int main() {

    #ifdef FIO
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
    #endif

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a1[i] >> b1[i];
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs(1, 0);

    for(int i = n; i >= 1; i--) {
        for(int j = 0; j <= m; j++) {
            f[i][j] = f[i + sz[i]][j];
            if(j >= b[i]) f[i][j] = max(f[i][j], f[i + 1][j - b[i]] + a[i]);
        }
    }

    cout << f[1][m] << '\n';

    return 0;
}