제출 #587215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587215		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<vector<long long>>> dp(n, vector<vector<long long>>(2, 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 += max(dp[u][0][1], dp[u][1][1]);
      f.push_back(w + max(dp[u][0][0], dp[u][0][1]) - max(dp[u][0][1], dp[u][1][1])); 
    }
    dp[v][0][1] = ft;            
    sort(f.rbegin(), f.rend());
    if ((int) f.size() >= 2) {
      dp[v][0][0] = max(ft, ft + f[0] + f[1]);
    } else {
      dp[v][0][0] = ft;
    }
    if ((int) f.size() >= 1) {
      dp[v][1][1] = ft + up + f[0];
    }                                           
  };
  Dfs(0, 0, 0);
  long long ans = max(dp[0][0][0], dp[0][0][1]);
  for (int i = 1; i < n; i++) {
    for (int p = 0; p < 2; p++) {
      for (int q = 0; q < 2; q++) {
        ans = max(ans, dp[i][p][q]);
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

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