oj.uz

Submission #978213

# Submission time Handle Problem Language Result Execution time Memory
978213 2024-05-09T03:41:39 Z duckindog Chase (CEOI17_chase) C++17
0 / 100
 111 ms 98792 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10,
          B = 100 + 10;
int n, b;
int a[N];
vector<int> ad[N];
int par[N];
long long dpdwd[N][B];
void dfs1(int u, int p = 0) { 
  par[u] = p;
  long long total = 0;
  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    total += a[v];
    dfs1(v, u);
  }
  
  dpdwd[u][1] = max(dpdwd[u][1], total + a[par[u]]);
  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    for (int i = 0; i <= b; ++i) { 
      auto& ret = dpdwd[u][i];
      ret = max(ret, dpdwd[v][i]);
      if (!i) continue;
      ret = max(ret, dpdwd[v][i - 1] + total - a[v] + a[par[u]]);
    }
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> b;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 2; i <= n; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }

  dfs1(1);
  
  long long answer = 0;
  for (int i = 1; i <= n; ++i) { 
    answer = max(answer, *max_element(dpdwd[i], dpdwd[i] + b + 1));
  }
  
  cout << answer << "\n";
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2804 KB Output is correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2804 KB Output is correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 98792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2804 KB Output is correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -