Submission #1108213

#TimeUsernameProblemLanguageResultExecution timeMemory
1108213abczzBeads and wires (APIO14_beads)C++17
100 / 100
181 ms36536 KiB
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

vector <array<ll, 2> > adj[200000];
ll n, a, b, c, dp[200000][2][2];

void dfs(ll u, ll p) {
  for (auto [v, x] : adj[u]) {
    if (v != p) dfs(v, u);
  }
  dp[u][0][1] = dp[u][1][0] = dp[u][1][1] = -1e18;
  vector <array<ll, 2>> V;
  for (auto [v, x] : adj[u]) {
    if (v == p) continue;
    V.push_back({dp[v][0][0] + x - max(dp[v][0][0], dp[v][0][1] + x), v});
    dp[u][0][0] += max(dp[v][0][0], dp[v][0][1] + x);
  }
  sort(V.begin(), V.end(), [](auto a, auto b) {
    return a[0] > b[0];
  });
  dp[u][1][0] = dp[u][0][0];
  for (auto [v, x] : adj[u]) {
    if (v == p) continue;
    dp[u][0][1] = max(dp[u][0][1], dp[u][0][0] - max(dp[v][0][0], dp[v][0][1] + x) + dp[v][0][0] + x);
    dp[u][1][0] = max(dp[u][1][0], dp[u][0][0] - max(dp[v][0][0], dp[v][0][1] + x) + max(dp[v][1][0], dp[v][1][1]+x));
    if (V[0][1] != v) dp[u][1][0] = max(dp[u][1][0], dp[u][0][0] - max(dp[v][0][0], dp[v][0][1] + x) + dp[v][1][0] + x + V[0][0]);
    else if (V.size() > 1) dp[u][1][0] = max(dp[u][1][0], dp[u][0][0] - max(dp[v][0][0], dp[v][0][1] + x) + dp[v][1][0] + x + V[1][0]);
  }
  for (auto [v, x] : adj[u]) {
    if (v == p) continue;
    dp[u][1][1] = max(dp[u][1][1], dp[u][0][0] - max(dp[v][0][0], dp[v][0][1] + x) + dp[v][1][0] + x);
  }
  /*cout << u+1 << " ";
  for (int i=0; i<2; ++i) {
    for (int j=0; j<2; ++j) {
      cout << dp[u][i][j] << " ";
    }
  }
  cout << endl;*/
}
int main() {
  cin >> n;
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b >> c;
    --a, --b;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  dfs(0, -1);
  cout << dp[0][1][0] << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...