제출 #1087709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087709		juicy	Chase (CEOI17_chase)	C++17	100 / 100	360 ms	174416 KiB

chase

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

int n, k;
int a[N];
long long s[N], f[N][101], g[N][101], dp[101];
vector<int> tr[N];

long long dfs(int u, int p) {
  long long res = 0;
  for (auto v : tr[u]) {
    if (v ^ p) {
      res = max(res, dfs(v, u));
    }
  }
  for (int i = 1; i <= k; ++i) {
    f[u][i] = dp[i] = s[u];
  }
  for (int v : tr[u]) {
    for (int i = 1; i <= k; ++i) {
      dp[i] = max({dp[i], dp[i - 1], f[v][i], f[v][i - 1] + s[u] - a[v]});
      g[u][i] = max({g[u][i], g[u][i - 1], g[v][i], g[v][i - 1] + s[u] - a[p]});
    }
    for (int i = 0; i <= k; ++i) {
      res = max(res, f[u][i] + g[v][k - i]);
      f[u][i] = dp[i];
    }
  }
  for (int i = 1; i <= k; ++i) {
    f[u][i] = dp[i] = s[u];
  }
  reverse(tr[u].begin(), tr[u].end());
  for (int v : tr[u]) {
    for (int i = 1; i <= k; ++i) {
      dp[i] = max({dp[i], dp[i - 1], f[v][i], f[v][i - 1] + s[u] - a[v]});
    }
    for (int i = 0; i <= k; ++i) {
      res = max(res, f[u][i] + g[v][k - i]);
      f[u][i] = dp[i];
    }
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    tr[u].push_back(v);
    tr[v].push_back(u);
    s[u] += a[v];
    s[v] += a[u];
  }
  cout << dfs(1, 1);
  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30