Submission #978213

#	Time	Username	Problem	Language	Result	Execution time	Memory
978213		duckindog	Chase (CEOI17_chase)	C++17	0 / 100	111 ms	98792 KiB

chase

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30