제출 #754344

#제출 시각아이디문제언어결과실행 시간메모리
754344thinknoexit구슬과 끈 (APIO14_beads)C++17
0 / 100
5 ms5028 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 200200; vector<pair<int, ll>> adj[N]; ll dp[2][N]; void dfs(int v, int p = 0) { ll mx = -4e10, mx2 = -4e10; ll sum = 0; for (auto& [x, w] : adj[v]) { if (x == p) continue; dfs(x, v); ll val = max(dp[0][x], dp[1][x] + w); sum += val; mx2 = max(mx2, dp[0][x] + w - val); if (mx < mx2) swap(mx, mx2); } dp[1][v] = sum + mx; dp[0][v] = max(sum, sum + mx + mx2); } int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; ll s = 0; for (int i = 1;i < n;i++) { int u, v; ll w; cin >> u >> v >> w; s += w; adj[u].push_back({ v,w }); adj[v].push_back({ u,w }); } dfs(1); while (dp[0][1] > s) { cout << dp[0][1] << '\n'; } cout << dp[0][1]; return 0; } /* 10 4 10 2 1 2 21 1 3 13 6 7 1 7 9 5 2 4 3 2 5 8 1 6 55 6 8 34 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...