自动搬运

查看原文

来自洛谷，原作者为

	gu51yo **

搬运于2025-08-24 23:13:01，当前版本为作者最后更新于2025-04-17 22:38:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

组合问题，观察到数据范围 $1000$，考虑树形 DP。因为每个节点的可能提供的值不确定，所以还需要利用分组背包来实现。

思路分析

状态定义

定义 $dp[u]$ 为 bitset 类型。例如 $dp[u][x] = true$ 表示在以节点 $u$ 为根的子树中，通过删除部分节点，可以使得子树提供恰好 $x$ 的价值。

状态转移

采用树形 DP 的经典形式，DFS，从叶子节点开始，自底向上。

• 叶子节点：

  只有两种状态。保留或删除，向父节点贡献 $w[u]$ 或 $0$ 价值。

• 非叶子节点：

  有多种状态，状态集合即它可能贡献的价值。设 $u$ 的子节点集合为 $g(u)$。$dp_u$ 即 $u$ 的子节点 $v$ 们的价值组合集合。

  再递归向上，直到根节点。这就是一个树上的，分组背包问题了。我们可以维护一个 bitset 来高效地解决这个问题。

时间复杂度

• DFS 遍历整棵树需要 $O(n)$ 时间。在每个非叶子节点 $u$，我们需要对其子节点 $v$ 的价值集合进行组合。总时间复杂度为 $O(n \cdot W^2)$。

  对于 $n=1000,W=1000$，理论时间复杂度是 $10^9$，但因为终止条件 $s+f \leq w[u]$ 会节省很多计算。实测运行效率远好于理论上界，即使不解绑同步，依然可以 200ms 通过此题。

• 实际上可以用位运算优化来降低时间复杂度。感谢 MattL 提出。同时感谢 Dr_Gilbert 的多次审核。

        for (int s = 0; s <= w[u]; s++) if (cur[s] == 1)    // 分组背包 DP, 未优化，O(W^2)
            for (int f = 0; s + f <= w[u]; f++)
                if (dp[v][f] == 1) nxt[s + f] = 1;

    for (int i = 0; i <= w[u]; ++i) mask.set(i); // mask存节点u的所有合法值
    ...
    ...
    for (int s = cur._Find_first(); s <= w[u]; s = cur._Find_next(s)) nxt |= (dp[v] << s);
    nxt &= mask;  // 避免位运算后出现非法值，&一下。位运算优化后，时间复杂度常数可以除以64。

具体实现详细见代码：

const int N = 1e3+9;
int n, ans=0;
vector<int> w(N);
vector<vector<int>> g(N);
vector<bitset<N>> dp(N);

void dfs(int u, int p) {
    if (g[u].size() == 1 && p != -1) {  // 叶子节点判断
        dp[u][0] = 1;
        if (w[u] <= N) dp[u][w[u]] = 1;
        return;
    }

    bitset<N> cur, mask; cur[0] = 1;
    for (int i = 0; i <= w[u]; ++i) mask.set(i);

    for (int v : g[u]) if (v != p) {
        dfs(v, u);
        bitset<N> nxt; nxt[0] = 1;
        for (int s = cur._Find_first(); s <= w[u]; s = cur._Find_next(s)) nxt |= (dp[v] << s);
        nxt &= mask;
        cur = nxt;
    }
    dp[u] = cur;
}

signed main () {
    cin >> n;   // 输入
    for (int i = 1; i <= n; i++) cin >> w[i];   
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }

    dfs(1, -1); // 树形 DP

    for (int x = w[1]; x >= 0; x--) if (dp[1][x] == 1) {ans = x; break;}    // 输出
    cout << ans << '\n';
}

值得一提的是，这可能是一道假题。因为题目并没有提到“若将 $u$ 的所有子节点都删除后，$u$ 不会因为转变为叶子节点而转变为产出材料”。