Submission #1149978

#TimeUsernameProblemLanguageResultExecution timeMemory
114997812345678구슬과 끈 (APIO14_beads)C++17
0 / 100
4 ms4936 KiB
#include <bits/stdc++.h> using namespace std; const int nx=2e5+5; int n, u, v, w, dp1[nx], dp2[nx]; vector<pair<int, int>> d[nx]; void dfs(int u, int p, int pw) { int sm=0; vector<pair<int, int>> c; for (auto [v, w]:d[u]) if (v!=p) dfs(v, u, w), dp1[u]+=dp2[v], sm+=dp2[v], c.push_back({v, w}); for (int i=0; i<c.size(); i++) { for (int j=i+1; j<c.size(); j++) { dp1[u]=max(dp1[u], sm-dp2[c[i].first]-dp2[c[j].first]+dp1[c[i].first]+dp1[c[j].first]+c[i].second+c[j].second); } } for (int i=0; i<c.size(); i++) dp2[u]=max(dp2[u], sm-dp2[c[i].first]+dp1[c[i].first]+c[i].second+pw); dp2[u]=max(dp2[u], dp1[u]); if (u==1&&0) { cout<<"debug "; for (auto x:c) cout<<x.first<<' '; cout<<'\n'; } //cout<<"u "<<u<<' '<<dp1[u]<<' '<<dp2[u]<<'\n'; } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n; for (int i=1; i<n; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w}); dfs(1, 1, 0); cout<<dp1[1]; } /* 11 34 35 95 0 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...