/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 1ms 532.0 KiB
#3 Wrong Answer 1ms 532.0 KiB

Code

#include <bits/stdc++.h>

using namespace std;

void solve(int cs) {
  int n, k;
  cin >> n >> k;
  vector<int64_t> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v; cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int64_t ans = 0;
  vector<vector<int64_t>> dp(n, vector<int64_t>(k, LLONG_MIN));
  auto dfs = [&](auto &&self, int node, int pr) -> void {
    dp[node][0] = a[node];
    for (auto &son : g[node]) {
      if (son ^ pr) {
        self(self, son, node);
        for (int i = k - 1; i > 0; --i) {
          for (int j = 0; j < i; j++) {
            if (dp[son][j] != LLONG_MIN) {
              dp[node][i] = max(dp[node][i], dp[node][i - j - 1] + dp[son][j]);
            }
          }
        }
      }
    }
  };
  dfs(dfs, 0, -1);
  for (int i = 0; i < n; i++) {
    ans = max(ans, dp[i][k - 1]);
  }
  cout << ans << "\n";
}

int32_t main() {
  ios::sync_with_stdio(!cin.tie(0));
  int t = 1;
  // cin >> t;
  for (int i = 1; i <= t; ++i) {
    solve(i);
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1161 Max path sum (Hard Version)
Contest
Brain Booster #8
Language
C++17 (G++ 13.2.0)
Submit At
2025-02-17 16:09:30
Judged At
2025-02-17 16:09:30
Judged By
Score
2
Total Time
1ms
Peak Memory
532.0 KiB