제출 #404020

#제출 시각아이디문제언어결과실행 시간메모리
404020opukittpceno_hhr구슬과 끈 (APIO14_beads)C++17
0 / 100
4 ms5016 KiB
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <string> #include <cmath> #include <cstdio> #include <iomanip> #include <fstream> #include <cassert> #include <cstring> #include <unordered_set> #include <unordered_map> #include <numeric> #include <ctime> #include <bitset> #include <complex> #include <chrono> #include <random> #include <functional> using namespace std; #define int long long const int INF = 1e18 + 239; const int N = 2e5 + 7; int to[N]; int dp[N][2]; vector<pair<int, int>> g[N]; void dfs(int cur, int p) { vector<int> sons; for (auto [t, w] : g[cur]) { if (t != p) { to[t] = w; sons.push_back(t); dfs(t, cur); } } if (sons.empty()) { dp[cur][0] = 0; dp[cur][1] = -INF; return; } dp[cur][0] = -INF; dp[cur][1] = -INF; // for (auto t : sons) { int c = 0; for (auto u : sons) { if (u == t) { c += dp[u][0]; c += to[u]; } else { c += max(dp[u][0], dp[u][1]); } } dp[cur][1] = max(dp[cur][1], c + to[cur]); } // { int c = 0; for (auto u : sons) { c += max(dp[u][0], dp[u][1]); } dp[cur][0] = max(dp[cur][0], c); } // sort(sons.begin(), sons.end(), [&](int f, int s) { return (dp[f][0] + to[f]) - max(dp[f][0], dp[f][1]) > (dp[s][0] + to[s]) - max(dp[s][0], dp[s][1]); }); if (sons.size() > 1) { int c = dp[sons[0]][0] + dp[sons[1]][0] + to[sons[0]] + to[sons[1]]; for (int i = 2; i < (int)sons.size(); i++) { c += max(dp[sons[i]][0], dp[sons[i]][1]); } dp[cur][0] = max(dp[cur][0], c); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 0; i + 1 < n; i++) { int u, v, w; cin >> u >> v >> w; u--; v--; g[u].push_back({v, w}); g[v].push_back({u, w}); } dfs(0, -1); cout << dp[0][0] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...