제출 #734265

#제출 시각아이디문제언어결과실행 시간메모리
734265Alihan_8구슬과 끈 (APIO14_beads)C++17
13 / 100
1 ms316 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define pb push_back #define ln '\n' #define int long long template <class _T> bool chmin(_T &x, const _T &y){ bool flag = false; if ( x > y ){ x = y; flag |= true; } return flag; } template <class _T> bool chmax(_T &x, const _T &y){ bool flag = false; if ( x < y ){ x = y; flag |= true; } return flag; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector <pair<int,int>> g[n]; for ( int i = 1; i < n; i++ ){ int x, y, w; cin >> x >> y >> w; g[--x].pb({--y, w}); g[y].pb({x, w}); } const int inf = 1e18 + 1; vector <array<int,2>> dp(n); function <void(int,int,int)> dfs = [&](int x, int par, int prev){ int cnt = 0, l = -inf, r = -inf; for ( auto [to, w]: g[x] ){ if ( to == par ) continue; dfs(to, x, w); cnt += dp[to][1]; int v = dp[to][0] - dp[to][1] + w; if ( l <= v ){ r = l; l = v; } else chmax(r, v); } dp[x][0] = cnt; dp[x][1] = l + cnt + max(prev, r); chmax(dp[x][1], dp[x][0]); }; int Mx = 0; for ( int i = 0; i < n; i++ ){ dfs(i, -1, 0); chmax(Mx, dp[i][0]); } cout << Mx; cout << '\n'; } /* 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...