This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
const ll MX = 2e9;
const ll N = 1e5 + 500;
int n, m;
ll a[510], f[510][510][2];
vector <int> g[510];
void upd(ll &a, ll b) { a = max(a, b); }
void dfs(int v, int pr) {
f[v][1][0] = a[v];
for (int u : g[v]) {
if (u == pr)
continue;
dfs(u, v);
for (int tv = m; tv > 0; --tv)
for (int tu = m; tu > 0; --tu) {
if (tv + tu + 2 <= m) {
upd(f[v][tv + tu + 2][0], f[v][tv][0] + f[u][tu][0]);
upd(f[v][tv + tu + 2][1], f[v][tv][1] + f[u][tu][0]);
}
if (tv + tu + 1 <= m)
upd(f[v][tv + tu + 1][1], f[v][tv][0] + max(f[u][tu][0], f[u][tu][1]));
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #ifdef _LOCAL
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
// #endif // _LOCAL
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(0, 0);
ll ans = 0;
for (int i = 0; i <= m; ++i)
for (int t = 0; t < 2; ++t)
upd(ans, f[0][i][t]);
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |