제출 #135074

#제출 시각아이디문제언어결과실행 시간메모리
135074fredbr구슬과 끈 (APIO14_beads)C++17
28 / 100
1061 ms1272 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 dp[maxn][2]; int cpt[maxn]; inline int invalid(int x, int p) { return v[x].size() == 1 and v[x].front().u == p; } 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& e : v[x]) { if (e.u == p) continue; if (!invalid(e.u, x)) { d += cpt[e.u] = max(solve(e.u, x, 1) + e.w, solve(e.u, x, 0)); } } } else { int sum = solve(x, p, 0); for (Edge& e : v[x]) { if (e.u == p) continue; if (!invalid(e.u, x)) d = max(d, sum - cpt[e.u] + e.w + solve(e.u, x, 0)); else d = max(d, sum + e.w); } } return dp[x][t] = d; } inline int test(int x) { memset(dp, -1, sizeof(dp)); return solve(x); } int main() { ios::sync_with_stdio(false), cin.tie(nullptr); int n; 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...