#define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) using vec4 = array<ll, 4>; constexpr ll INF = 1e18; constexpr int MAX_OFFSET = 1536; mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); vector<vector<Pii>> G; ll dp[2][2][MAX_OFFSET*2+64]; vec4 solve(int v, int p, ll wp) { vector<vec4> parts; each(e, G[v]) if (e.x != p) { parts.pb(solve(e.x, v, e.y)); } int offset = min(sz(parts)/2+4, MAX_OFFSET); int lim = offset*2 + 4; shuffle(all(parts), rnd); rep(b, 0, 2) fill(dp[1][b], dp[1][b]+lim, -INF); dp[1][0][offset] = 0; rep(i, 0, sz(parts)) { auto part = parts[i]; rep(b, 0, 2) { auto &cur = dp[i&1][b], &prv0 = dp[~i&1][b], &prv1 = dp[~i&1][!b]; rep(j, 0, lim) cur[j] = max(prv0[j] + part[0], prv1[j] + part[2]); rep(j, 1, lim) cur[j] = max(cur[j], prv0[j-1] + part[1]); rep(j, 0, lim-1) cur[j] = max(cur[j], prv0[j+1] + part[3]); } } auto &cur = dp[~sz(parts) & 1]; return { max(cur[0][offset], cur[0][offset-1] + wp), cur[0][offset] + wp, cur[0][offset+1] + wp, cur[1][offset] + wp, }; } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(12); int n; cin >> n; G.resize(n); rep(i, 1, n) { int u, v, w; cin >> u >> v >> w; G[u-1].pb({v-1, w}); G[v-1].pb({u-1, w}); } cout << solve(0, -1, -INF)[0] << '\n'; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) using vec4 = array<ll, 4>; constexpr ll INF = 1e18; constexpr int MAX_OFFSET = 1536; mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); vector<vector<Pii>> G; ll dp[2][2][MAX_OFFSET*2+64]; vec4 solve(int v, int p, ll wp) { vector<vec4> parts; each(e, G[v]) if (e.x != p) { parts.pb(solve(e.x, v, e.y)); } int offset = min(sz(parts)/2+4, MAX_OFFSET); int lim = offset*2 + 4; shuffle(all(parts), rnd); rep(b, 0, 2) fill(dp[1][b], dp[1][b]+lim, -INF); dp[1][0][offset] = 0; rep(i, 0, sz(parts)) { auto part = parts[i]; rep(b, 0, 2) { auto &cur = dp[i&1][b], &prv0 = dp[~i&1][b], &prv1 = dp[~i&1][!b]; rep(j, 0, lim) cur[j] = max(prv0[j] + part[0], prv1[j] + part[2]); rep(j, 1, lim) cur[j] = max(cur[j], prv0[j-1] + part[1]); rep(j, 0, lim-1) cur[j] = max(cur[j], prv0[j+1] + part[3]); } } auto &cur = dp[~sz(parts) & 1]; return { max(cur[0][offset], cur[0][offset-1] + wp), cur[0][offset] + wp, cur[0][offset+1] + wp, cur[1][offset] + wp, }; } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(12); int n; cin >> n; G.resize(n); rep(i, 1, n) { int u, v, w; cin >> u >> v >> w; G[u-1].pb({v-1, w}); G[v-1].pb({u-1, w}); } cout << solve(0, -1, -INF)[0] << '\n'; return 0; } |