树形dp

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <typeinfo>
#include <unordered_map>
#include <vector>
// #include "B.h"

using namespace std;

typedef long long ll;

int n;
int head[6004], cnt, par[6004][2];

struct E{
    int to, next;
};

E e[6004];

void add(int u, int v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void dfs(int c) {
  for (int i = head[c]; i != -1; i = e[i].next) {
    int v = e[i].to;
    dfs(v);
    par[c][1] += par[v][0];
    par[c][0] += max(par[v][0], par[v][1]);
  }
}

int happy[6004], vis[6004];

int main() {
  
  cin >> n;
  
  for (int i = 1; i <= n; ++i) {
    cin >> par[i][1];
  }


  std::fill(head, head + n + 1, -1);
  for (int i = 1; i <= n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    add(v, u);
    vis[u] = 1;
  }

  int root = 1;
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {
      root = i;
      break;
    }
  }
  dfs(root);
  cout << max(par[root][0], par[root][1]) << endl;
}

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <typeinfo>
#include <unordered_map>
#include <vector>
// #include "B.h"

using namespace std;

typedef long long ll;

int n, m, score[304], vis[304];
int head[304], cnt, fa[304][304];

struct E{
    int to, next;
};

E e[6004];

void add(int u, int v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

int dfs(int c) {
  int p = 1;
  fa[c][1] = score[c];
  for (int i = head[c]; i != -1; i = e[i].next) {
    int v = e[i].to;
    int sz = dfs(v);
    for (int j = min(p, m + 1); j >= 1; j--) {
      for (int k = 1; k + j <= m + 1 && k <= sz; ++k) {
        fa[c][j + k] = max(fa[c][j + k], fa[c][j] + fa[v][k]);
      }
    }
    p += sz;
  }
  return p;
}

int main() {
  cin >> n >> m;

  std::fill(head, head + n + 1, -1);
  for (int i = 1; i <= n; ++i) {
    int s, k;
    cin >> k >> score[i];
    add(k, i);
  }
  dfs(0);
  cout << fa[0][m + 1] << endl;
}