Submission #115818

#	Time	Username	Problem	Language	Result	Execution time	Memory
115818		IOrtroiii	Chase (CEOI17_chase)	C++14	100 / 100	639 ms	168592 KiB

chase

/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*/
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int N = 100100;
const int K = 110;

int n, k;
int a[N];
vector<int> g[N];
ll go[N];
ll up[N][K];
ll down[N][K];
ll ans = 0;

void dfs(int u, int p) {
   for (int v : g[u]) if (v != p) {
      dfs(v, u);
   }
   down[u][1] = go[u];
   for (int v : g[u]) if (v != p) {
      for (int i = 1; i <= k; ++i) {
         up[u][i] = max(up[u][i], max(up[v][i], up[v][i - 1] + go[u] - a[p]));
         down[u][i] = max(down[u][i], max(down[v][i], down[v][i - 1] + go[u] - a[v]));
         ans = max(ans, up[v][i - 1] + go[u]);
         ans = max(ans, down[v][i - 1] + go[u] - a[v]);
      }
   }
   for (int i = 0; i <= k; ++i) {
      pair<ll, ll> mx = {0, 0};
      for (int v : g[u]) if (v != p) {
         mx.second = max(mx.second, up[v][i]);
         if (mx.second > mx.first) {
            swap(mx.first, mx.second);
         }
      }
      for (int v : g[u]) if (v != p) {
         ll cur;
         if (up[v][i] == mx.first) {
            cur = mx.second;
         } else {
            cur = mx.first;
         }
         ans = max(ans, cur + down[v][k - i]);
      }
   }
   for (int i = 1; i <= k; ++i) {
      pair<ll, ll> mx = {0, 0};
      for (int v : g[u]) if (v != p) {
         mx.second = max(mx.second, up[v][i - 1]);
         if (mx.second > mx.first) {
            swap(mx.first, mx.second);
         }
      }
      for (int v : g[u]) if (v != p) {
         ll cur;
         if (up[v][i - 1] == mx.first) {
            cur = mx.second;
         } else {
            cur = mx.first;
         }
         ans = max(ans, cur + down[v][k - i] + go[u] - a[v]);
      }
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n >> k;
   if (k == 0) {
      cout << 0 << endl;
      return 0;
   }
   for (int i = 1; i <= n; ++i) {
      cin >> a[i];
   }
   for (int i = 1; i < n; ++i) {
      int u, v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
      go[u] += a[v];
      go[v] += a[u];
   }
   dfs(1, 0);
   cout << ans << endl;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30