# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
483090 | ntabc05101 | Chase (CEOI17_chase) | C++17 | 342 ms | 218700 KiB |
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;
const int mxN = 100005;
const int mxV = 105;
int n, v;
long long P[mxN];
long long dp[mxN][mxV][2];
vector<int> adj[mxN];
long long sum[mxN];
long long res = 0;
void dfs(int u, int p = 0) {
for (auto &to: adj[u]) {
if (to != p) {
dfs(to, u);
for (int i = 1; i <= v; i++) {
/*dp[u][i][1] = max(dp[u][i][1], max(dp[to][i][0], dp[to][i - 1][0] + sum[to] - P[u]));
if (dp[u][i][1] > dp[u][i][0]) {
swap(dp[u][i][1], dp[u][i][0]);
}*/
long long val = max(dp[to][i][0], dp[to][i - 1][0] + sum[to] - P[u]);
if (val > dp[u][i][0]) {
dp[u][i][1] = dp[u][i][0]; dp[u][i][0] = val;
}
else {
if (val > dp[u][i][1]) {
dp[u][i][1] = val;
}
}
}
}
}
}
void dfs2(int u, int p = 0) {
for (int i = 1; i <= v; i++) {
res = max(res, max(dp[u][i][0], dp[u][i - 1][0] + sum[u]));
}
for (auto &to: adj[u]) {
if (to != p) {
long long tmp[v + 1];
for (int i = 1; i <= v; i++) {
tmp[i] = dp[u][i][0];
if (max(dp[to][i][0], dp[to][i - 1][0] + sum[to] - P[u]) == dp[u][i][0]) {
dp[u][i][0] = dp[u][i][1];
}
}
for (int i = 1; i <= v; i++) {
/*dp[to][i][1] = max(dp[to][i][1], max(dp[u][i][0], dp[u][i - 1][0] + sum[u] - P[to]));
if (dp[to][i][1] > dp[to][i][0]) {
swap(dp[to][i][1], dp[to][i][0]);
}*/
long long val = max(dp[u][i][0], dp[u][i - 1][0] + sum[u] - P[to]);
if (val > dp[to][i][0]) {
dp[to][i][1] = dp[to][i][0]; dp[to][i][0] = val;
}
else {
if (val > dp[to][i][1]) {
dp[to][i][1] = val;
}
}
}
dfs2(to, u);
for (int i = 1; i <= v; i++) {
dp[u][i][0] = tmp[i];
}
}
}
}
int main() {
if (fopen("input.txt", "r")) {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
cin >> n >> v;
for (int i = 1; i <= n; i++) {
cin >> P[i];
}
for (int i = 0, x, y; i < n - 1; i++) {
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
for (auto &to: adj[i]) {
sum[i] += P[to];
}
}
dfs(1); dfs2(1);
cout << res << "\n";
return 0;
}
Compilation message (stderr)
# | 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... |