#include <stdio.h> #include <vector> #include <algorithm> #include <random> #include <chrono> #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) using ll=long long; using namespace std; const int C=200001, D=1751, E=2, H=(D-1)/2; const ll Inf = 1000000000000000000ll; int s[C], is=0, ip=1, pre[C], apre[C], par[C], ji[C]; ll value[C]; void proc_tree(int a, int n, vector <vector <int> > &tr, vector <vector <ll> > &ew){ s[0]=a, is=1, pre[a]=1, apre[1]=a, ip=2; int b; for(int z=1; z<=n; z++) ji[z]=tr[z].size(), par[z]=0; while (is>0){ a=s[is-1]; if (ji[a]>0 && tr[a][ji[a]-1]==par[a]) ji[a]--; if (ji[a]>0){ b=s[is]=tr[a][ji[a]-1]; value[b] = ew[a][ji[a]-1]; pre[b]=ip, apre[ip]=b; par[b]=a; ip++, is++, ji[a]--; } else is--; } } vector <vector <int> > tr(C); vector <vector <ll> > ew(C); bool exists[D][2], tmp_exists[D][2], valid_res[C][4]; ll dp[D][2], tmp_dp[D][2], res[C][4]; int main(){ mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int a, b, n, i, ln, j, s1, s2; ll w; bool valid=false; scanf ("%d", &n); for (i=1; i<n; i++){ scanf ("%d %d %lld", &a, &b, &w); tr[a].push_back(b), tr[b].push_back(a); ew[a].push_back(w), ew[b].push_back(w); } proc_tree(1, n, tr, ew); int parity, oddity; for (i=n; i>0; i--){ a = apre[i]; std::shuffle(tr[a].begin(), tr[a].end(), rng); //randomized children order ln = tr[a].size(); s1 = MAX(0, H-ln-2); s2 = MIN(D, H+ln+2); for (oddity=s1; oddity<s2; oddity++){ for (parity=0; parity<2; parity++){ dp[oddity][parity] = -Inf; exists[oddity][parity] = false; } } dp[H][0] = 0, exists[H][0] = true; for (j=0; j<ln; j++){ b = tr[a][j]; if (par[a]==b) continue; s1 = MAX(0, H-j-2); s2 = MIN(D, H+j+2); for (oddity=s1; oddity<s2; oddity++){ for (parity=0; parity<2; parity++){ tmp_dp[oddity][parity] = dp[oddity][parity]; tmp_exists[oddity][parity] = exists[oddity][parity]; } } for (oddity=s1; oddity<s2; oddity++){ for (parity=0; parity<2; parity++){ valid = false; if (exists[oddity][parity] && valid_res[b][0]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][0]+dp[oddity][parity]), valid=true; //Move I: don't add any edge, profit off max if (exists[oddity][parity] && valid_res[b][3]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][3]+value[b]+dp[oddity][parity]), valid=true; //Move V: add an edge of length 3+1, no merging with anything other if (exists[oddity][1-parity] && valid_res[b][1]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][1]+value[b]+dp[oddity][1-parity]), valid=true; //Move III: Symmetric movement, add 1+1+two edges between if (oddity>0 && exists[oddity-1][parity] && valid_res[b][0]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][0]+value[b]+dp[oddity-1][parity]), valid=true; //Move II: one from this branch, three from second branch if (oddity<D-1 && exists[oddity+1][parity] && valid_res[b][2]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][2]+value[b]+dp[oddity+1][parity]), valid=true; //Move V: three from this branch, one from second branch tmp_exists[oddity][parity] = valid; } } for (oddity=s1; oddity<s2; oddity++){ for (parity=0; parity<2; parity++){ dp[oddity][parity] = tmp_dp[oddity][parity]; exists[oddity][parity] = tmp_exists[oddity][parity]; } } } if (exists[H][0]) res[a][0] = dp[H][0], valid_res[a][0]=true; if (exists[H+1][0]) res[a][1] = dp[H+1][0], valid_res[a][1]=true; if (exists[H][1]) res[a][2] = dp[H][1], valid_res[a][2]=true; if (exists[H-1][0]) res[a][3] = dp[H-1][0], valid_res[a][3]=true; } printf ("%lld\n", res[1][0]); 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 | #include <stdio.h> #include <vector> #include <algorithm> #include <random> #include <chrono> #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) using ll=long long; using namespace std; const int C=200001, D=1751, E=2, H=(D-1)/2; const ll Inf = 1000000000000000000ll; int s[C], is=0, ip=1, pre[C], apre[C], par[C], ji[C]; ll value[C]; void proc_tree(int a, int n, vector <vector <int> > &tr, vector <vector <ll> > &ew){ s[0]=a, is=1, pre[a]=1, apre[1]=a, ip=2; int b; for(int z=1; z<=n; z++) ji[z]=tr[z].size(), par[z]=0; while (is>0){ a=s[is-1]; if (ji[a]>0 && tr[a][ji[a]-1]==par[a]) ji[a]--; if (ji[a]>0){ b=s[is]=tr[a][ji[a]-1]; value[b] = ew[a][ji[a]-1]; pre[b]=ip, apre[ip]=b; par[b]=a; ip++, is++, ji[a]--; } else is--; } } vector <vector <int> > tr(C); vector <vector <ll> > ew(C); bool exists[D][2], tmp_exists[D][2], valid_res[C][4]; ll dp[D][2], tmp_dp[D][2], res[C][4]; int main(){ mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int a, b, n, i, ln, j, s1, s2; ll w; bool valid=false; scanf ("%d", &n); for (i=1; i<n; i++){ scanf ("%d %d %lld", &a, &b, &w); tr[a].push_back(b), tr[b].push_back(a); ew[a].push_back(w), ew[b].push_back(w); } proc_tree(1, n, tr, ew); int parity, oddity; for (i=n; i>0; i--){ a = apre[i]; std::shuffle(tr[a].begin(), tr[a].end(), rng); //randomized children order ln = tr[a].size(); s1 = MAX(0, H-ln-2); s2 = MIN(D, H+ln+2); for (oddity=s1; oddity<s2; oddity++){ for (parity=0; parity<2; parity++){ dp[oddity][parity] = -Inf; exists[oddity][parity] = false; } } dp[H][0] = 0, exists[H][0] = true; for (j=0; j<ln; j++){ b = tr[a][j]; if (par[a]==b) continue; s1 = MAX(0, H-j-2); s2 = MIN(D, H+j+2); for (oddity=s1; oddity<s2; oddity++){ for (parity=0; parity<2; parity++){ tmp_dp[oddity][parity] = dp[oddity][parity]; tmp_exists[oddity][parity] = exists[oddity][parity]; } } for (oddity=s1; oddity<s2; oddity++){ for (parity=0; parity<2; parity++){ valid = false; if (exists[oddity][parity] && valid_res[b][0]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][0]+dp[oddity][parity]), valid=true; //Move I: don't add any edge, profit off max if (exists[oddity][parity] && valid_res[b][3]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][3]+value[b]+dp[oddity][parity]), valid=true; //Move V: add an edge of length 3+1, no merging with anything other if (exists[oddity][1-parity] && valid_res[b][1]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][1]+value[b]+dp[oddity][1-parity]), valid=true; //Move III: Symmetric movement, add 1+1+two edges between if (oddity>0 && exists[oddity-1][parity] && valid_res[b][0]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][0]+value[b]+dp[oddity-1][parity]), valid=true; //Move II: one from this branch, three from second branch if (oddity<D-1 && exists[oddity+1][parity] && valid_res[b][2]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][2]+value[b]+dp[oddity+1][parity]), valid=true; //Move V: three from this branch, one from second branch tmp_exists[oddity][parity] = valid; } } for (oddity=s1; oddity<s2; oddity++){ for (parity=0; parity<2; parity++){ dp[oddity][parity] = tmp_dp[oddity][parity]; exists[oddity][parity] = tmp_exists[oddity][parity]; } } } if (exists[H][0]) res[a][0] = dp[H][0], valid_res[a][0]=true; if (exists[H+1][0]) res[a][1] = dp[H+1][0], valid_res[a][1]=true; if (exists[H][1]) res[a][2] = dp[H][1], valid_res[a][2]=true; if (exists[H-1][0]) res[a][3] = dp[H-1][0], valid_res[a][3]=true; } printf ("%lld\n", res[1][0]); return 0;} |