제출 #135128

#제출 시각아이디문제언어결과실행 시간메모리
135128fredbr구슬과 끈 (APIO14_beads)C++17
0 / 100
2 ms636 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; int const maxn = 10001; struct Edge { int u, w; }; vector<Edge> v[maxn]; int n; int dp[maxn][2]; inline int invalid(int x) { return v[x].size() == 1; } int solve(int x, int p = -1, int t = 0) { if (dp[x][t] >= 0) return dp[x][t]; int d = 0; if (t == 0) { for (Edge const& e : v[x]) { if (e.u == p) continue; if (!invalid(e.u)) { d += max(solve(e.u, x, 1) + e.w, solve(e.u, x, 0)); } } } else { int sum = solve(x, p, 0); for (Edge const& e : v[x]) { if (e.u == p) continue; if (!invalid(e.u)) d = max(d, sum - max(solve(e.u, x, 1) + e.w, solve(e.u, x, 0)) + e.w + solve(e.u, x, 0)); else d = max(d, sum + e.w); } } return dp[x][t] = d; } vector<int> bfs_order(int ini) { vector<int> vis(n+1); queue<int> q {{ini}}; vis[ini] = 1; vector<int> res; while (!q.empty()) { int x = q.front(); res.push_back(x); q.pop(); for (Edge const& e : v[x]) { if (vis[e.u]) continue; vis[x] = 1; q.push(e.u); } } reverse(res.begin(), res.end()); return res; } inline int test(int ini) { memset(dp, 0, sizeof(dp)); auto order = bfs_order(ini); vector<int> vis(n+1); for (int x : order) { vis[x] = 1; int d = 0; for (Edge const& e : v[x]) { if (!vis[e.u]) continue; if (!invalid(e.u)) { d += max(dp[1][e.u] + e.w, dp[0][e.u]); } } dp[0][x] = d; d = 0; int sum = dp[0][x]; for (Edge const& e : v[x]) { if (!vis[e.u]) continue; if (!invalid(e.u)) d = max(d, sum - max(dp[1][e.u] + e.w, dp[0][e.u]) + e.w + dp[0][e.u]); else d = max(d, sum + e.w); } dp[1][x] = d; } return dp[0][ini]; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr); cin >> n; for (int i = 0; i < n-1; i++) { int a, b, w; cin >> a >> b >> w; v[a].push_back({b, w}); v[b].push_back({a, w}); } int ans = 0; for (int i = 1; i <= n; i++) if (v[i].size() == 1) ans = max(ans, test(i)); cout << ans << "\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...