제출 #957397

#제출 시각아이디문제언어결과실행 시간메모리
957397vjudge1구슬과 끈 (APIO14_beads)C++14
13 / 100
3 ms6748 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e5+10, inf=1e18; int f[N][2][2][2]; vector<pair<int, int>> g[N]; void dfs(int u, int p){ for (int i=0; i<8; ++i) f[u][!!(i&1)][!!(i&2)][!!(i&4)]=-inf; for (auto &e:g[u]) if (e.first!=p) dfs(e.first, u); vector<int> sum(2); for (int cu=0; cu<=1; ++cu){ for (auto &e:g[u]) if (e.first!=p){ int mx=-inf; for (int t=0; t<=1; ++t) for (int cv=0; cv<=(!cu || t); ++cv) mx=max(mx, f[e.first][t][cu][cv]); sum[cu]+=mx; } } f[u][0][0][0]=sum[0]; vector<vector<pair<int, int>>> tmp(2); for (auto &e:g[u]) if (e.first!=p){ int mx1=-inf; for (int t=0; t<=1; ++t) for (int cv=0; cv<=t; ++cv) mx1=max(mx1, f[e.first][t][1][cv]); for (int cv=0; cv<=1; ++cv){ tmp[cv].emplace_back(f[e.first][0][1][cv]+e.second-mx1, e.first); } } sort(tmp[0].rbegin(), tmp[0].rend()); sort(tmp[1].rbegin(), tmp[1].rend()); if ((int)tmp[0].size()>=2){ for (int t0=0; t0<=1; ++t0) for (int t1=t0; t1<=1; ++t1) if (!(t0&t1)){ if (tmp[t0][0].second!=tmp[t1][0].second) f[u][0][0][1]=max(f[u][0][0][1], sum[1]+tmp[t0][0].first+tmp[t1][0].first); if (tmp[t0][0].second!=tmp[t1][1].second) f[u][0][0][1]=max(f[u][0][0][1], sum[1]+tmp[t0][0].first+tmp[t1][1].first); if (tmp[t0][1].second!=tmp[t1][0].second) f[u][0][0][1]=max(f[u][0][0][1], sum[1]+tmp[t0][1].first+tmp[t1][0].first); } } f[u][0][1][0]=f[u][0][0][0]; f[u][0][1][1]=f[u][0][0][1]; if (p){ int wpar=0; for (auto &e:g[p]) if (e.first==u) wpar=e.second; tmp[0].clear(); tmp[1].clear(); for (auto &e:g[u]) if (e.first!=p){ int mx1=-inf; for (int t=0; t<=1; ++t) for (int cv=0; cv<=t; ++cv) mx1=max(mx1, f[e.first][t][1][cv]); for (int cv=0; cv<=1; ++cv){ tmp[cv].emplace_back(f[e.first][0][1][cv]+e.second+wpar-mx1, e.first); } } sort(tmp[0].rbegin(), tmp[0].rend()); sort(tmp[1].rbegin(), tmp[1].rend()); if (tmp[0].size()){ f[u][1][0][1]=sum[1]+max(tmp[0][0].first, tmp[1][0].first); f[u][1][1][1]=sum[1]+tmp[0][0].first; } } } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i=1; i<n; ++i){ int u, v, w; cin >> u >> v >> w; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } dfs(1, 0); cout << max(f[1][0][0][0], f[1][0][0][1]); 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...