Submission #255290

#	Time	Username	Problem	Language	Result	Execution time	Memory
255290		rama_pang	Beads and wires (APIO14_beads)	C++14	28 / 100	1089 ms	5760 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][2]; // dp[u][do we use parent edge?]

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

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);
  }

  lint ans = 0;
  for (int i = 0; i < N; i++) {
    Dfs(i);
    ans = max(ans, dp[i][0]);
  }
  cout << ans << "\n";
  return 0;
}

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