CFR 815 C. Karen and Supermarket

Problem Description:
There are N items, the i'th item costs C[i], and we have a coupon that can reduce its price by D[i]. However, for every coupon i to be effective, coupon X[i] must be used, i.e., i'th item bought. You have B units of money as your budget, find the maximum number of items you can buy.

Constraints:
1 ≤ N ≤ 5000
1 ≤ B ≤ 1e9
1 ≤ D[i] ≤ C[i] ≤ 1e9

Solution:
Not only does the dependency constitute a DAG, it is a rooted tree. We can come up with a DP solution:
dp[0][u][x]: minimum cost to buy x items, considering subtree with root u, given that u's father was not bought
dp[1][u][x]: minimum cost to buy x items, considering subtree with root u, given that u's father was bought
dp[2][u][x] = min(dp[0][u][x], dp[1][u][x])
T(u): time cost for subtree with root u
T(u) = u.chlidren.map { |v| T(v) } .inject(:+) + u.children.map { |v| v.size } .inject(:*)
However, as u.size ≥ u.children.map { |v| v.size } .inject(:+), and u.size ** 2 ≥ u.children.map { |v| v.size ** 2 } .inject(:+) + u.children.map { |v| v.size } .inject(:*), we can deduce that T(u) = O(u.size ** 2).

Code:

#include <bits/stdc++.h>

int Dp(int n, int b, const std::vector<int> &c, const std::vector<int> &d, const std::vector<int> &x) {
  std::vector<std::vector<int>> graph(n);
  for (int i = 1; i < n; ++i) {
    graph[x[i] - 1].emplace_back(i);
  }
  std::vector<std::vector<int>> dp[3];
  std::for_each(dp, dp + 3, [&](std::vector<std::vector<int>> &v) { v.resize(n); });
  std::function<void(int)> dfs = [&](int u) {
    dp[0][u] = { 0, c[u] };
    dp[1][u] = { 0x3f3f3f3f, c[u] - d[u] };
    for (int v : graph[u]) {
      dfs(v);
      auto merge = [&](const std::vector<int> &a, const std::vector<int> &b) {
        std::vector<int> c(a.size() + b.size() - 1, 0x3f3f3f3f);
        for (size_t i = 0; i < a.size(); ++i) {
          for (size_t j = 0; j < b.size(); ++j) {
            c[i + j] = std::min(c[i + j], a[i] + b[j]);
          }
        }
        return c;
      };
      dp[0][u] = merge(dp[0][u], dp[0][v]);
      dp[1][u] = merge(dp[1][u], dp[2][v]);
    }
    dp[2][u].resize(dp[0][u].size());
    std::for_each(dp[2][u].begin(), dp[2][u].end(), [&, i = 0](int &x) mutable { x = std::min(dp[0][u][i], dp[1][u][i]), ++i; });
  };
  dfs(0);
  return dp[2][0].size() - 1 - std::distance(dp[2][0].rbegin(), std::find_if(dp[2][0].rbegin(), dp[2][0].rend(), [&](int w) { return w <= b; }));
}

signed main() {
  std::ios::sync_with_stdio(false);
  int N, B;
  std::cin >> N >> B;
  std::vector<int> C(N), D(N), X(N);
  for (int i = 0; i < N; ++i) {
    std::cin >> C[i] >> D[i];
    if (i) std::cin >> X[i];
  }
  std::cout << Dp(N, B, C, D, X) << std::endl;
  return 0;
}