Submission #587204

#	Time	Username	Problem	Language	Result	Execution time	Memory
587204		MilosMilutinovic	Beads and wires (APIO14_beads)	C++14	0 / 100	1 ms	212 KiB

beads

/**
 *    author:  wxhtzdy
 *    created: 01.07.2022 14:47:42
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    --u; --v;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);  
  }
  vector<vector<long long>> dp(n, vector<long long>(2));   
  function<void(int, int, int)> Dfs = [&](int v, int pr, int up) {
    vector<long long> f;
    long long ft = 0;
    for (auto& p : g[v]) {
      int u = p.first;
      int w = p.second;
      if (u == pr) {
        continue;
      }
      Dfs(u, v, w);                                  
      ft += dp[u][1];
      f.push_back(w + dp[u][0] - dp[u][1]); 
    }
    dp[v][0] = ft;            
    for (int it = 0; it < 2; it++) {
      sort(f.rbegin(), f.rend());
      long long s = 0;
      for (int i = 0; i + 1 < (int) f.size() && i < 2; i += 2) {
        s += f[i] + f[i + 1];
        dp[v][it] = max(dp[v][it], ft + s);
      }
      f.push_back(up);
    }
  };
  Dfs(0, 0, 0);
  long long ans = dp[0][0];
  for (int i = 1; i < n; i++) {
    ans = max(ans, max(dp[i][0], dp[i][1]));
  }
  cout << dp[0][0] << '\n';
  return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43