Submission #255317

#	Time	Username	Problem	Language	Result	Execution time	Memory
255317		rama_pang	Beads and wires (APIO14_beads)	C++14	100 / 100	641 ms	51800 KiB

beads

#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const int MAXN = 2e5 + 5;
const lint INF = 1e18;

int N;
vector<pair<int, int>> adj[MAXN];

lint dp[MAXN];
multiset<lint> mx[MAXN];

long long ans = 0;

void Dfs(int u, int p = -1) {
  dp[u] = 0;
  mx[u].emplace(-INF);
  for (auto e : adj[u]) if (e.first != p) {
    int v = e.first;
    int w = e.second;
    Dfs(v, u);
    dp[u] += max(dp[v], w + dp[v] + *prev(end(mx[v])));
    mx[u].emplace(dp[v] + w - max(dp[v], w + dp[v] + *prev(end(mx[v]))));
  }
}

void Reroot(int u, int p = -1) {
  ans = max(ans, dp[u]);
  for (auto e : adj[u]) if (e.first != p) {
    int v = e.first;
    int w = e.second;

    dp[u] -= max(dp[v], w + dp[v] + *prev(end(mx[v])));
    mx[u].erase(mx[u].find(dp[v] + w - max(dp[v], w + dp[v] + *prev(end(mx[v])))));

    dp[v] += max(dp[u], w + dp[u] + *prev(end(mx[u])));
    mx[v].emplace(dp[u] + w - max(dp[u], w + dp[u] + *prev(end(mx[u]))));

    Reroot(v, u);

    dp[v] -= max(dp[u], w + dp[u] + *prev(end(mx[u])));
    mx[v].erase(mx[v].find(dp[u] + w - max(dp[u], w + dp[u] + *prev(end(mx[u])))));

    dp[u] += max(dp[v], w + dp[v] + *prev(end(mx[v])));
    mx[u].emplace(dp[v] + w - max(dp[v], w + dp[v] + *prev(end(mx[v]))));
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N;
  for (int i = 0; i + 1 < N; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  Dfs(0), Reroot(0);
  cout << ans << "\n";
  return 0;
}

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