LOJ #160. 树形背包 题解

Description

有 \(N\) 个物品，编号分别为 \(1\ldots N\)。物品 \(i\) 的重量为 \(w_i\)，价值为 \(v_i\)。

给出每个物品依赖于哪个物品。我们用 \(d_i = j\ (i>j>0)\) 表示：如果要选取物品 \(i\)，就必须先选取物品 \(j\)。另外，我们用 \(d_i = 0 (i>0)\) 表示：该物品不依赖于任何物品。保证每个物品最多只依赖一个物品。保证依赖关系合理，不会出现环。

背包最多能装载的重量为 \(W\)，请问背包中最多能装入多大价值的物品。

\(1\le N×W\le 6×10^7, 1\le N\le 5×10^4, 0\le W\le 6×10^4\)

\(1\le w_i\le 200,0\le v_i\le 5000\)

Solution

题目的限制相当于是要求出一个包含根的连通块使得重量之和不超过 \(W\)，并且让价值之和最大。

可以设 \(f_{i,j}\) 表示 \(i\) 的子树里包含 \(i\) 的连通块重量之和为 \(j\) 的最大价值。容易做到 \(O(NW^2)\)。

上面那个做法慢在要做 \(N\) 次背包合并，单次背包合并就是 \(O(W^2)\) 的，所以要找到一个不需要背包合并的做法。

考虑按照 dfs 序从后往前 dp。

假设当前枚举到了 \(x\)，则把 dfs 序大于等于 \(x\) 的点拿出来一定构成若干个子树，并且这些子树互不相交。如果在这些点中选出一些不存在依赖关系问题的点，那么每个子树一定选了一个包含根的连通块。

设 \(f_{i,j}\) 表示 dfs 序大于等于 \(i\) 的点构成重量和为 \(j\) 且不出现依赖关系问题的最大权值。

如果 \(i\) 选，则后面只要不存在问题，加入 \(i\) 后仍不出现问题，所以 \(f_{i,j}\leftarrow f_{i+1,j-w_i}+v_i\)。

如果 \(i\) 不选，则 \(i\) 的子树也不选，所以 \(f_{i,j}\leftarrow f_{i+sz_i,j}\)。

答案即为 \(\max_{0\leq i\leq W}\{f_{1,i}\}\)。

时间复杂度：\(O(NW)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 5e4 + 5, kMaxT = 6.1e7 + 5;

int n, m;
int p[kMaxN], w[kMaxN], v[kMaxN], pool[kMaxT];
int dfn[kMaxN], sz[kMaxN], idx[kMaxN];
std::vector<int> G[kMaxN];

void dfs(int u) {
  static int cnt = 0;
  idx[dfn[u] = ++cnt] = u, sz[u] = 1;
  for (auto v : G[u]) {
    dfs(v);
    sz[u] += sz[v];
  }
}

void dickdreamer() {
  std::cin >> n >> m;
  memset(pool, 0xcf, sizeof(pool));
  int (&f)[n + 2][m + 1] = decltype(f)(pool);
  for (int i = 1; i <= n; ++i) {
    std::cin >> p[i];
    if (p[i]) G[p[i]].emplace_back(i);
  }
  for (int i = 1; i <= n; ++i) std::cin >> w[i];
  for (int i = 1; i <= n; ++i) std::cin >> v[i];
  for (int i = 1; i <= n; ++i)
    if (!p[i])
      dfs(i);
  f[n + 1][0] = 0;
  for (int i = n; i; --i) {
    for (int j = m; ~j; --j) {
      f[i][j] = f[i + sz[idx[i]]][j];
      if (j >= w[idx[i]]) f[i][j] = std::max(f[i][j], f[i + 1][j - w[idx[i]]] + v[idx[i]]);
    }
  }
  std::cout << *std::max_element(f[1], f[1] + 1 + m) << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}