제출 #670189

#제출 시각아이디문제언어결과실행 시간메모리
670189Radin_Zahedi2구슬과 끈 (APIO14_beads)C++17
0 / 100
3 ms4948 KiB
#include<bits/stdc++.h> //#pragma GCC optimize("O2") using namespace std; using ll = long long; using ld = long double; #define pb push_back #define mp make_pair #define fi first #define se second #define sz(x) (int)x.size() #define endl '\n' const int mod = 1e9 + 7; const int inf = 2e9 + 5; const ll linf = 9e18 + 5; int n; const int N = 2e5 + 5; vector<pair<int, int>> adj[N]; int dp[N][2]; void dfs(int u, int p) { vector<int> toinde; int desum = 0; int pw = 0; for (auto e : adj[u]) { int v = e.fi; int w = e.se; if (v != p) { dfs(v, u); if (dp[v][1] == -1) { toinde.pb(dp[v][0] + w); } else { toinde.pb(dp[v][0] + w - dp[v][1]); } desum += max(dp[v][0], dp[v][1]); } else { pw = w; } } int maxi[2] = {-inf, -inf}; for (auto x : toinde) { if (x > maxi[0]) { maxi[1] = maxi[0]; maxi[0] = x; } else if (x > maxi[1]) { maxi[1] = x; } } dp[u][0] = desum; if (maxi[1] != -inf) { dp[u][0] = max(dp[u][0], desum + maxi[0] + maxi[1]); } if (maxi[0] != -inf) { dp[u][1] = desum + maxi[0] + pw; } else { dp[u][1] = -1; } } void init() { } void input() { cin >> n; for (int i = 1; i < n; i++) { int u, v, c; cin >> u >> v >> c; adj[u].pb(mp(v, c)); adj[v].pb(mp(u, c)); } } void solve() { dfs(1, 0); cout << dp[1][0]; } void output() { } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int number_of_testcases = 1; //cin >> number_of_testcases; while (number_of_testcases--) { init(); input(); solve(); output(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...