#pragma GCC optimize ("Ofast") #define _USE_MATH_DEFINES #include <bits/stdc++.h> #define FOR(i, a, b) for (auto i=(a); i<(b); i++) #define FORD(i, a, b) for (int i=(a); i>(b); i--) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define PPC(x) __builtin_popcountll(x) #define MSB(x) (63 - __builtin_clzll(x)) #define LSB(x) __builtin_ctz(x) #define ARG(x, i) (get<i>(x)) #define ithBit(m, i) ((m) >> (i) & 1) #define pb push_back #define ft first #define sd second #define kw(a) ((a) * (a)) #ifdef DEBUG #include "debug.h" #else #define dbg(...) 0 #endif using namespace std; template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b); } template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b); } const int maxN = 1 << 18; const long long INF = 1'0000'0000'0000'0000; vector <pair <int, int> > G[maxN]; long long dp[maxN][4]; int state[maxN]; long long T[maxN][2][2]; void go(int v) { int I = 1, s = SZ(G[v]) / 2 + 1; FOR(i, -1, s+1) FOR(a, 0, 2) FOR(b, 0, 2) T[I + i][a][b] = -INF; T[I + 0][0][0] = 0; FOR(i, 1, SZ(G[v])+1) { int u = G[v][i-1].ft; int a = i & 1, z = a ^ 1, mx = min(i, s); FOR(j, -1, mx + 1) FOR(d, 0, 2) { auto& x = T[I + j][a][d]; x = T[I + j][z][d] + dp[u][1]; if (j != mx) remax(x, T[I + j+1][z][d] + dp[u][0]); if (j != -1) remax(x, T[I + j-1][z][d] + dp[u][2]); remax(x, T[I + j][z][d ^ 1] + dp[u][3]); } } s = SZ(G[v]) & 1; dp[v][0] = T[I + 0][s][0]; dp[v][1] = T[I + 1][s][0]; dp[v][2] = T[I + 0][s][1]; dp[v][3] = T[I - 1][s][0]; } void dfs(int v, int fat = 0) { FOR(i, 0, SZ(G[v])) { int u = G[v][i].ft; if (u == fat) { swap(G[v][i], G[v].back()); G[v].pop_back(); i--; continue; } dfs(u, v); } sort(ALL(G[v]), [] (auto& a, auto& b) { int u = a.ft, w = b.ft; return dp[u][2] - dp[u][0] > dp[w][2] - dp[w][0]; }); for (auto [u, e] : G[v]) { dp[u][1] += e; remax(dp[u][1], dp[u][0]); state[u] = 1; FOR(i, 0, 4) if (i != 1) { dp[u][i] += e; if (dp[u][i] > dp[u][state[u]]) state[u] = i; } } go(v); } void solve() { int n; scanf ("%d", &n); FOR(i, 1, n) { int a, b, c; scanf ("%d%d%d", &a, &b, &c); G[a].pb({b, c}); G[b].pb({a, c}); } dfs(1, 0); printf("%lld\n", dp[1][0]); } int main() { int t = 1; //scanf ("%d", &t); FOR(tid, 1, t+1) { //printf("Case #%d: ", tid); solve(); } 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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #pragma GCC optimize ("Ofast") #define _USE_MATH_DEFINES #include <bits/stdc++.h> #define FOR(i, a, b) for (auto i=(a); i<(b); i++) #define FORD(i, a, b) for (int i=(a); i>(b); i--) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define PPC(x) __builtin_popcountll(x) #define MSB(x) (63 - __builtin_clzll(x)) #define LSB(x) __builtin_ctz(x) #define ARG(x, i) (get<i>(x)) #define ithBit(m, i) ((m) >> (i) & 1) #define pb push_back #define ft first #define sd second #define kw(a) ((a) * (a)) #ifdef DEBUG #include "debug.h" #else #define dbg(...) 0 #endif using namespace std; template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b); } template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b); } const int maxN = 1 << 18; const long long INF = 1'0000'0000'0000'0000; vector <pair <int, int> > G[maxN]; long long dp[maxN][4]; int state[maxN]; long long T[maxN][2][2]; void go(int v) { int I = 1, s = SZ(G[v]) / 2 + 1; FOR(i, -1, s+1) FOR(a, 0, 2) FOR(b, 0, 2) T[I + i][a][b] = -INF; T[I + 0][0][0] = 0; FOR(i, 1, SZ(G[v])+1) { int u = G[v][i-1].ft; int a = i & 1, z = a ^ 1, mx = min(i, s); FOR(j, -1, mx + 1) FOR(d, 0, 2) { auto& x = T[I + j][a][d]; x = T[I + j][z][d] + dp[u][1]; if (j != mx) remax(x, T[I + j+1][z][d] + dp[u][0]); if (j != -1) remax(x, T[I + j-1][z][d] + dp[u][2]); remax(x, T[I + j][z][d ^ 1] + dp[u][3]); } } s = SZ(G[v]) & 1; dp[v][0] = T[I + 0][s][0]; dp[v][1] = T[I + 1][s][0]; dp[v][2] = T[I + 0][s][1]; dp[v][3] = T[I - 1][s][0]; } void dfs(int v, int fat = 0) { FOR(i, 0, SZ(G[v])) { int u = G[v][i].ft; if (u == fat) { swap(G[v][i], G[v].back()); G[v].pop_back(); i--; continue; } dfs(u, v); } sort(ALL(G[v]), [] (auto& a, auto& b) { int u = a.ft, w = b.ft; return dp[u][2] - dp[u][0] > dp[w][2] - dp[w][0]; }); for (auto [u, e] : G[v]) { dp[u][1] += e; remax(dp[u][1], dp[u][0]); state[u] = 1; FOR(i, 0, 4) if (i != 1) { dp[u][i] += e; if (dp[u][i] > dp[u][state[u]]) state[u] = i; } } go(v); } void solve() { int n; scanf ("%d", &n); FOR(i, 1, n) { int a, b, c; scanf ("%d%d%d", &a, &b, &c); G[a].pb({b, c}); G[b].pb({a, c}); } dfs(1, 0); printf("%lld\n", dp[1][0]); } int main() { int t = 1; //scanf ("%d", &t); FOR(tid, 1, t+1) { //printf("Case #%d: ", tid); solve(); } return 0; } |