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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_int_distribution<long long>(a, b)(rng)

#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define f first
#define s second
#define pb push_back

#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vi>
#define vvii vector<vii>

#define ll long long


const int N = 1e6 + 7;
const ll INF = 1e18;

vvii G(N);

ll DP[N][4]; // Maksymalna punktacja za drzewo [ukorzenione w jakimś wierzchołku][takie że rozpoczęto w nim ścieżkę jakiejś długości]

const int MID = 2000;
ll TEMP[2][MID * 2][2]; // pierwszy wymiar jest jedynie po to by zaoszczędzić pamięć
// Maksymalny wynik dla prefiks synów, 
// [][Jeżeli mam rozpoczęte i - MID ścieżek długości 1 (dla ujemnych długości 3)][zostala mi jedna wisząca ścieżka długości 2, lub też nie]

void dfs(int start, int przodek = -1){
    vector<ii> syny;
    syny.reserve(sz(G[start]));
    for(auto & [u, v] : G[start])
        if(u != przodek)
            syny.pb({u, v});

    shuffle(all(syny), rng); // to jest kluczowe!
    for(auto & [u, v] : syny)
        dfs(u, start);

    int shift = 1000; // pewnie można mniej (3 * sqrt(sz(sons))??), ale nie chcę świrować
    
    // WYZROWUJĘ TABLICĘ
    for(int bit = 0; bit < 2; bit++)
        for(int bilans = MID - shift - 5; bilans <= MID + shift + 5; bilans++) // z lekkim zapasikiem
            for(int zostau = 0; zostau < 2; zostau++)
                TEMP[bit][bilans][zostau] = -INF;

    TEMP[1][MID][0] = 0; // nie biorę niczego, nigdy

    for(int i = 0; i < sz(syny); i++){
        int a = i & 1; // aktualna kolumna TEMP
        int b = a ^ 1; // poprzednia kolumna TEMP

        // wyzeruj aktualną kolumnę
        for(int bilans = MID - shift - 5; bilans <= MID + shift + 5; bilans++) // z lekkim zapasikiem
            for(int zostau = 0; zostau < 2; zostau++)
                TEMP[a][bilans][zostau] = -INF;

        // rozważam trywialne pominięcie krawędzi tego syna

        for(int bilans = MID - shift; bilans <= MID + shift; bilans++)
            for(int zostau = 0; zostau < 2; zostau++)
                TEMP[a][bilans][zostau] = max(TEMP[a][bilans][zostau], TEMP[b][bilans][zostau] + DP[syny[i].f][0]);

        // rozważam ruch, w którym biorę starą ścieżkę długości 3 z syna
        // To dość prosta możliwość, bo po prostu dodaję jedną nową
        // krawędź kończąc ścieżkę długości 4

        for(int bilans = MID - shift; bilans <= MID + shift; bilans++)
            for(int zostau = 0; zostau < 2; zostau++)
                TEMP[a][bilans][zostau] = max(TEMP[a][bilans][zostau], TEMP[b][bilans][zostau] + DP[syny[i].f][3] + syny[i].s);
        
        // rozważam ruch, w którym biorę starą ścieżkę długości 1 z syna
        // To przejście też jest dość proste, bo obserwujemy, że albo
        // utworzymy nowo wiszącą odnogę długości dwa, albo ją dopasujemy
        // to już istniejącej odnogi

        for(int bilans = MID - shift; bilans <= MID + shift; bilans++)
            for(int zostau = 0; zostau < 2; zostau++)
                TEMP[a][bilans][zostau] = max(TEMP[a][bilans][zostau], TEMP[b][bilans][zostau ^ 1] + DP[syny[i].f][1] + syny[i].s);
        
        // Zostały dwa najtrudniejsze przejścia

        // Przypadek w którym w nowo wybrany synie nie ma zagnieżdżonej
        // ścieżki - albo inaczej, ma długość 0, wtedy tworzymy odnogę 
        // długości 1 i albo możemy ją połączyć z jakąś odnogą z przeszłości
        // albo dodajemy ją do już istniejących odnóg (których nie ma nigdy za dużo) 

        for(int bilans = MID - shift; bilans <= MID + shift; bilans++)
            for(int zostau = 0; zostau < 2; zostau++)
                // wcześniej miałem stan [b][bilans][zostau]
                TEMP[a][bilans + 1][zostau] = max(TEMP[a][bilans + 1][zostau], TEMP[b][bilans][zostau] + DP[syny[i].f][0] + syny[i].s);        
        
        // ostatni ruch symetryczny do poprzedniego przypadku
        for(int bilans = MID - shift; bilans <= MID + shift; bilans++)
            for(int zostau = 0; zostau < 2; zostau++)
                // wcześniej miałem stan [b][bilans][zostau]
                TEMP[a][bilans - 1][zostau] = max(TEMP[a][bilans - 1][zostau], TEMP[b][bilans][zostau] + DP[syny[i].f][2] + syny[i].s);        
    }

    int ind = (sz(syny) + 1) & 1; // intuicyjnie -1 ale może być ujemna
    
    // wyliczanie właściwych stanów DP
    DP[start][0] = TEMP[ind][MID][0];
    DP[start][1] = TEMP[ind][MID + 1][0];
    DP[start][2] = TEMP[ind][MID][1];
    DP[start][3] = TEMP[ind][MID - 1][0];
}

void solve(){
    int n;
    cin >> n;


    for(int i = 0; i < n - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;

        a--, b--;

        G[a].pb({b, c});
        G[b].pb({a, c});
    }

    dfs(0);
    cout << DP[0][0] << '\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tests = 1;
    // cin >> tests;

    for(int i = 0; i < tests; i++)
        solve();

    return 0;
}