Codeforces 815C. Karen and Supermarket【树形DP】

LINK

---

思路

首先发现依赖关系是一个树形的结构

然后因为直接算花多少钱来统计贡献不是很好

因为数组开不下

那就可以算一个子树里面选多少个的最小代价就可以了

注意统计贡献的时候用优惠券的答案只能在1号点进行统计

---

//Author: dream_maker

#include<bits/stdc++.h>

using namespace std;

//----------------------------------------------

//typename

typedef long long ll;

//convenient for

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

//inf of different typename

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

//fast read and write

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

const int N = 5010;

struct Edge{

  int v, nxt;

}E[N << 1];

int head[N], tot = 0;

ll c[N], d[N], siz[N], n;

ll dp[N][N][2], ans = 0, B;

void add(int u, int v) {

  E[++tot] = (Edge){v, head[u]};

  head[u] = tot;

}

void dfs(int u, int fa) {

  siz[u] = 1;

  dp[u][1][1] = c[u] - d[u];

  dp[u][1][0] = c[u];

  for (int i = head[u]; i; i = E[i].nxt) {

    int v = E[i].v;

    if (v == fa) continue;

    dfs(v, u);

    fd(j, siz[u], 0)

      fd(k, siz[v], 0) {

        dp[u][j + k][1] = min(dp[u][j + k][1], dp[u][j][1] + min(dp[v][k][0], dp[v][k][1]));

        dp[u][j + k][0] = min(dp[u][j + k][0], dp[u][j][0] + dp[v][k][0]);

      }

    siz[u] += siz[v];

  }

  fu(i, ans + 1, siz[u]) {

    if (dp[u][i][0] <= B) ans = i;

    else break;

  }

}

int main() {

  memset(dp, 0x3f, sizeof(dp));

  Read(n); Read(B);

  fu(i, 1, n) {

    Read(c[i]); Read(d[i]);

    dp[i][0][0] = 0;

    if (i > 1) {

      int u; Read(u);

      add(i, u);

      add(u, i);

    }

  }

  dfs(1, 0);

  fu(i, ans + 1, n) if (dp[1][i][1] <= B) ans = i;

  Write(ans);

  return 0;

}