Submission #1108209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108209		abczz	Beads and wires (APIO14_beads)	C++17	0 / 100	2 ms	6992 KiB

beads

#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][0][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';
}

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