#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define sz(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
#define cint int&
using namespace std;
const int nax = 505;
void maxi(int &a, const int b) {
a = max(a, b);
}
int n, m;
int a, b;
int cost[nax];
vector <int> g[nax];
int dp[nax][nax][2][2];
int dp2[nax][2][2];
// 0 to musze wrocic -> 0
// 1 to nie musze -> 0 / 1
void dfs(int v, int p) {
rep(i, 0, m)
rep(a, 0, 1)
rep(b, 0, 1)
dp[v][i][a][b] = -1e9;
dp[v][0][0][0] = 0;
dp[v][0][1][0] = 0;
dp[v][1][0][0] = cost[v];
dp[v][1][1][0] = cost[v];
for (auto it : g[v]) {
if (it == p) continue;
dfs(it, v);
rep(i, 0, m)
rep(a, 0, 1)
rep(b, 0, 1)
dp2[i][a][b] = dp[v][i][a][b];
int s, e;
rep(i, 0, m)
rep(j, 0, m - i)
rep(a, 0, 1)
rep(b, 0, 1) {
if (a == 0 && b == 1) continue;
rep(c, 0, 1) {
if (a == 0 && c == 1) continue;
if (a == 1 && b == 1 && c == 1) continue;
if (a == 0 && c == 0) {
s = i + j + 2;
if (s <= m) maxi(dp2[s][0][0], dp[v][i][a][b] + dp[it][j][c][0]);
}
if (a == 1) {
e = (b | c);
s = i + j + 1 + !(c == 1);
if (s <= m) maxi(dp2[s][1][e], dp[v][i][a][b] + max(dp[it][j][c][0], dp[it][j][c][1]));
}
}
}
rep(i, 0, m)
rep(a, 0, 1)
rep(b, 0, 1)
dp[v][i][a][b] = dp2[i][a][b];
}
}
int main() {
scanf ("%d%d", &n, &m);
rep(i, 1, n) scanf ("%d", cost + i);
rep(i, 1, n - 1) {
scanf ("%d%d", &a, &b);
g[a].pb(b);
g[b].pb(a);
}
dfs(1, 0);
int res = 0;
rep(i, 0, m)
rep(a, 0, 1)
rep(b, 0, 1)
maxi(res, dp[1][i][a][b]);
printf ("%d\n", res);
return 0;
}
Compilation message
dostavljac.cpp: In function 'int main()':
dostavljac.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &n, &m);
~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:83:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
rep(i, 1, n) scanf ("%d", cost + i);
~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:85:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &a, &b);
~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
19 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
1152 KB |
Output is correct |
| 2 |
Correct |
244 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
435 ms |
2128 KB |
Output is correct |
| 2 |
Correct |
143 ms |
1888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
2424 KB |
Output is correct |
| 2 |
Correct |
1016 ms |
2756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
863 ms |
3440 KB |
Output is correct |
| 2 |
Correct |
340 ms |
3596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1660 ms |
4272 KB |
Output is correct |
| 2 |
Correct |
164 ms |
3576 KB |
Output is correct |
