This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int MAX_N = 502;
const int INF = 1e9;
int n, m, a[MAX_N];
vector<int> f[MAX_N][MAX_N][2];
vector<int> g[MAX_N];
void enter() {
cin >> n >> m;
for (int i=1; i<=n; ++i)
cin >> a[i];
g[1].push_back(0);
for (int i=1; i<n; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
}
void fix_root(int u, int par) {
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i];
if (v==par)
swap(g[u][0], g[u][i]);
else
fix_root(v, u);
}
}
void init_dp() {
for (int u=1; u<=n; ++u)
for (int i=0; i<=m; ++i)
for (int j=0; j<2; ++j)
f[u][i][j].resize(g[u].size(), -1);
}
int dp(int u, int total_time, bool come_back, int child_id) {
if (total_time<0) {
return -INF;
}
if (child_id == 0) {
return 0;
}
if (child_id == g[u].size()) {
return max(dp(u, total_time, come_back, child_id-1),
dp(u, total_time-1, come_back, child_id-1) + a[u]);
}
if (f[u][total_time][come_back][child_id]!=-1)
return f[u][total_time][come_back][child_id];
int res = dp(u, total_time, come_back, child_id - 1);
int v = g[u][child_id];
for (int time_for_v=1; time_for_v<=total_time; ++time_for_v) {
res = max(res, dp(u, total_time-time_for_v-2, come_back, child_id-1)
+ dp(v, time_for_v, true, g[v].size()));
if (!come_back) {
res = max(res, dp(u, total_time-time_for_v-1, true, child_id-1)
+ dp(v, time_for_v, false, g[v].size()));
}
}
return f[u][total_time][come_back][child_id] = res;
}
int main() {
//#define OFFLINE_JUDGE doraemon
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
enter();
fix_root(1, 0);
//PR0(g[1], g[1].size());
init_dp();
//debug(dp(1, 1, false, 1));
cout << dp(1, m, false, g[1].size());
}
Compilation message (stderr)
dostavljac.cpp: In function 'void fix_root(int, int)':
dostavljac.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
dostavljac.cpp: In function 'int dp(int, int, bool, int)':
dostavljac.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (child_id == g[u].size()) {
~~~~~~~~~^~~~~~~~~~~~~~
# | 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... |