#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 200200; const ll inf = 1LL * 1000100100 * 1000100100; int n,m; vector<pii> g[N]; int vert[N], par[N]; ll dp[N][4]; ll D[2][4][2][2][N*2]; void dfs(int u, int parent = -1) { FOR(i,SZ(g[u])) { int v = g[u][i].fi; if (v == parent) { par[u] = v; } else { dfs(v, u); } } vert[m++] = u; } int vvs[N]; int main() { scanf("%d", &n); FOR(i,n-1) { int a,b,c; scanf("%d%d%d", &a, &b, &c); //a=1; b=i+2; c=rand()%1000000-500000; a--; b--; g[a].emplace_back(b,c); g[b].emplace_back(a,c); } FOR(i,n) random_shuffle(g[i].begin(), g[i].end()); dfs(0); FOR(i,n) vvs[i]=SZ(g[i]); sort(vvs,vvs+n); //cerr << vvs[n-1] << " " << vvs[n-2] << " " << vvs[n-3] << "\n"; int MAXMAXTWOS = 10000, posmx = n-1; ll MAXOP = 4e7; while (posmx>=0 && vvs[posmx]>=1e4) posmx--; ll totalop_min = 0, totalop_max = 1; FOR(i,n) { if (i <= posmx) totalop_min += 1LL*vvs[i]*vvs[i]; else totalop_max += vvs[i]; } while (totalop_min + totalop_max*vvs[posmx] > MAXOP) { //cerr << totalop_min << " + " << totalop_max << " * " << vvs[posmx] << " is too much\n"; totalop_min -= 1LL*vvs[posmx]*vvs[posmx]; totalop_max += vvs[posmx]; posmx--; } MAXMAXTWOS = (MAXOP-totalop_min) / totalop_max; //cerr << totalop_min << " + " << totalop_max << " * " << vvs[posmx] << " is ok\n"; //cerr << totalop_min << " + " << totalop_max << " * " << MAXMAXTWOS << " is ok\n"; ll totalop = 0; FOR(ii,n) { int u = vert[ii]; int VTWOS = min(SZ(g[u]) / 2, MAXMAXTWOS), MAXTWOS = VTWOS * 2 + 1; totalop += 1LL * MAXTWOS * SZ(g[u]); //int VTWOS = SZ(g[u]) / 2, MAXTWOS = VTWOS * 2 + 1; FOR(L,4) FOR(top,2) FOR(ones,2) FOR(twos,MAXTWOS) { D[0][L][top][ones][twos] = -inf; D[1][L][top][ones][twos] = -inf; } FOR(L,4) D[0][L][0][0][0+VTWOS] = 0; FOR(i,SZ(g[u])) { int v = g[u][i].fi, c = g[u][i].se; if (v == par[u]) continue; // D[layer=0/1][L=0..3][top=0/1][ones=0/1][twos=-N..N] FORI(L,3) FOR(ones,2) FOR(twos,MAXTWOS) { D[1][L][1][ones][twos] = max(D[1][L][1][ones][twos], D[0][L][0][ones][twos] + c + dp[v][L-1]); } FOR(L,4) FOR(top,2) FOR(ones,2) FOR(twos,MAXTWOS) { ll DC = D[0][L][top][ones][twos]; D[1][L][top][ones][twos] = max(D[1][L][top][ones][twos] , DC + max(c + dp[v][3], dp[v][0])); if (twos+1<MAXTWOS) D[1][L][top][ones][twos+1] = max(D[1][L][top][ones][twos+1], DC + c + dp[v][2] ); if (twos > 0) D[1][L][top][ones][twos-1] = max(D[1][L][top][ones][twos-1], DC + c + dp[v][0] ); D[1][L][top][!ones][twos] = max(D[1][L][top][!ones][twos] , DC + c + dp[v][1] ); } FOR(L,4) FOR(top,2) FOR(ones,2) FOR(twos,MAXTWOS) { D[0][L][top][ones][twos] = D[1][L][top][ones][twos]; D[1][L][top][ones][twos] = -inf; } } dp[u][0] = D[0][0][0][0][VTWOS]; FORI(L,3) dp[u][L] = D[0][L][1][0][VTWOS]; } printf("%lld\n", dp[0][0]); //cout << totalop << "\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 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 | #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 200200; const ll inf = 1LL * 1000100100 * 1000100100; int n,m; vector<pii> g[N]; int vert[N], par[N]; ll dp[N][4]; ll D[2][4][2][2][N*2]; void dfs(int u, int parent = -1) { FOR(i,SZ(g[u])) { int v = g[u][i].fi; if (v == parent) { par[u] = v; } else { dfs(v, u); } } vert[m++] = u; } int vvs[N]; int main() { scanf("%d", &n); FOR(i,n-1) { int a,b,c; scanf("%d%d%d", &a, &b, &c); //a=1; b=i+2; c=rand()%1000000-500000; a--; b--; g[a].emplace_back(b,c); g[b].emplace_back(a,c); } FOR(i,n) random_shuffle(g[i].begin(), g[i].end()); dfs(0); FOR(i,n) vvs[i]=SZ(g[i]); sort(vvs,vvs+n); //cerr << vvs[n-1] << " " << vvs[n-2] << " " << vvs[n-3] << "\n"; int MAXMAXTWOS = 10000, posmx = n-1; ll MAXOP = 4e7; while (posmx>=0 && vvs[posmx]>=1e4) posmx--; ll totalop_min = 0, totalop_max = 1; FOR(i,n) { if (i <= posmx) totalop_min += 1LL*vvs[i]*vvs[i]; else totalop_max += vvs[i]; } while (totalop_min + totalop_max*vvs[posmx] > MAXOP) { //cerr << totalop_min << " + " << totalop_max << " * " << vvs[posmx] << " is too much\n"; totalop_min -= 1LL*vvs[posmx]*vvs[posmx]; totalop_max += vvs[posmx]; posmx--; } MAXMAXTWOS = (MAXOP-totalop_min) / totalop_max; //cerr << totalop_min << " + " << totalop_max << " * " << vvs[posmx] << " is ok\n"; //cerr << totalop_min << " + " << totalop_max << " * " << MAXMAXTWOS << " is ok\n"; ll totalop = 0; FOR(ii,n) { int u = vert[ii]; int VTWOS = min(SZ(g[u]) / 2, MAXMAXTWOS), MAXTWOS = VTWOS * 2 + 1; totalop += 1LL * MAXTWOS * SZ(g[u]); //int VTWOS = SZ(g[u]) / 2, MAXTWOS = VTWOS * 2 + 1; FOR(L,4) FOR(top,2) FOR(ones,2) FOR(twos,MAXTWOS) { D[0][L][top][ones][twos] = -inf; D[1][L][top][ones][twos] = -inf; } FOR(L,4) D[0][L][0][0][0+VTWOS] = 0; FOR(i,SZ(g[u])) { int v = g[u][i].fi, c = g[u][i].se; if (v == par[u]) continue; // D[layer=0/1][L=0..3][top=0/1][ones=0/1][twos=-N..N] FORI(L,3) FOR(ones,2) FOR(twos,MAXTWOS) { D[1][L][1][ones][twos] = max(D[1][L][1][ones][twos], D[0][L][0][ones][twos] + c + dp[v][L-1]); } FOR(L,4) FOR(top,2) FOR(ones,2) FOR(twos,MAXTWOS) { ll DC = D[0][L][top][ones][twos]; D[1][L][top][ones][twos] = max(D[1][L][top][ones][twos] , DC + max(c + dp[v][3], dp[v][0])); if (twos+1<MAXTWOS) D[1][L][top][ones][twos+1] = max(D[1][L][top][ones][twos+1], DC + c + dp[v][2] ); if (twos > 0) D[1][L][top][ones][twos-1] = max(D[1][L][top][ones][twos-1], DC + c + dp[v][0] ); D[1][L][top][!ones][twos] = max(D[1][L][top][!ones][twos] , DC + c + dp[v][1] ); } FOR(L,4) FOR(top,2) FOR(ones,2) FOR(twos,MAXTWOS) { D[0][L][top][ones][twos] = D[1][L][top][ones][twos]; D[1][L][top][ones][twos] = -inf; } } dp[u][0] = D[0][0][0][0][VTWOS]; FORI(L,3) dp[u][L] = D[0][L][1][0][VTWOS]; } printf("%lld\n", dp[0][0]); //cout << totalop << "\n"; return 0; } |