제출 #166529

#제출 시각아이디문제언어결과실행 시간메모리
166529combi1k1구슬과 끈 (APIO14_beads)C++14
0 / 100
8 ms5112 KiB
#include<bits/stdc++.h> using namespace std; #define pb emplace_back #define int long long const int N = 2e5 + 1; typedef pair<int,int> ii; vector<ii> g[N]; int f[N][2]; void dfs(int u,int p) { int mx1 = -1e9; int mx2 = -1e9; f[u][0] = 0; for(ii e : g[u]) { int v = e.first; int c = e.second; if (v == p) continue; dfs(v,u); f[u][0] += max(f[v][1] + c,f[v][0]); if (mx2 < min(c,f[v][0] - f[v][1])) mx2 = min(c,f[v][0] - f[v][1]); if (mx1 < mx2) swap(mx1,mx2); } f[u][1] = f[u][0] + mx1; f[u][0] = f[u][0] + max(mx1 + mx2,0ll); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i = 1 ; i < n ; ++i) { int x; cin >> x; int y; cin >> y; int c; cin >> c; g[x].pb(y,c); g[y].pb(x,c); } int ans = 0; for(int i = 1 ; i <= n ; ++i) { dfs(i,0); ans = max(ans,f[i][0]); } cout << ans << endl; } /* 5 1 2 10 1 3 40 1 4 15 1 5 20 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...