Submission #173785

#	Time	Username	Problem	Language	Result	Execution time	Memory
173785		fedoseevtimofey	Beads and wires (APIO14_beads)	C++17	0 / 100	6 ms	5112 KiB

beads

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <cassert>
#include <complex>
#include <functional>
 
using namespace std;
 
typedef long long ll;

const int N = 2e5 + 7;

vector <pair <int, int>> g[N];

int dp[N][2];

void dfs(int u, int p, int wp) {
  int sum = 0;
  vector <int> vals;
  for (auto [v, w] : g[u]) {
    if (v != p) {
      dfs(v, u, w);
      sum += dp[v][1];
      vals.push_back(dp[v][0] + w - dp[v][1]);
    }
  }
  dp[u][0] = sum;
  sort(vals.rbegin(), vals.rend());
  if (vals.size() >= 2) {
    dp[u][0] = max(dp[u][0], sum + vals[0] + vals[1]);
  }
  if (p != -1 && vals.size() >= 1) {
    dp[u][1] = sum + vals[0] + wp;
  }
  dp[u][1] = max(dp[u][1], dp[u][0]);
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  for (int i = 0; i + 1 < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  dfs(0, -1, 0);
  cout << dp[0][1] << '\n';
}

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