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
#include <iostream>
#include <vector>
#include <tuple>

using namespace std;
typedef long long ll;

int n;
vector<vector<pair<int, ll>>> edges;

void set_parent(int v, int p) {
    int ppos = -1;
    for (int i = 0; i < (int)edges[v].size(); i++) {
        int x = edges[v][i].first;
        if (x == p) ppos = i;
        else set_parent(x, v);
    }
    if (ppos != -1) edges[v].erase(edges[v].begin() + ppos);
}

ll DP[200000][4];

void do_step(ll (*out)[2], ll (*prev)[2], int kmax, ll *w) {
    for (int k = -kmax-1; k <= kmax+1; k++) {
        out[k][0] = out[k][1] = -4e18;
    }

#define M(t, v) t = max(t, v)
    for (int k = -kmax; k <= kmax; k++) {
        for (int p = 0; p < 2; p++) {
            M(out[k][p], prev[k][p] + w[0]);
            M(out[k+1][p], prev[k][p] + w[1]);
            M(out[k][p^1], prev[k][p] + w[2]);
            M(out[k-1][p], prev[k][p] + w[3]);
        }
    }
}

void calc(int v) {
    for (auto [w, c] : edges[v]) {
        calc(w);
    }

    int deg = edges[v].size();
    int shift = deg + 5;
    ll (*buf1)[2] = (ll (*)[2])malloc((2 * shift) * 2 * sizeof(ll));
    ll (*buf2)[2] = (ll (*)[2])malloc((2 * shift) * 2 * sizeof(ll));
    buf1 += shift;
    buf2 += shift;

    for (int i = 0; i < 4; i++) {
        for (int k = -1; k <= 1; k++) {
            buf1[k][0] = buf1[k][1] = -4e18;
        }

        switch(i) {
        case 0: buf1[0][0] = 0; break;
        case 1: buf1[-1][0] = 0; break;
        case 2: buf1[0][1] = 0; break;
        case 3: buf1[1][0] = 0; break;
        }

        int kmax = 1;

        for (auto [w, c] : edges[v]) {
            ll W[4];
            W[0] = max(DP[w][0], DP[w][3] + c);
            W[1] = DP[w][0] + c;
            W[2] = DP[w][1] + c;
            W[3] = DP[w][2] + c;
            do_step(buf2, buf1, kmax++, W);
            swap(buf1, buf2);
        }

        DP[v][i] = buf1[0][0];
        //cerr << "DP[" << v << "][" << i << "] = " << DP[v][i] << endl;
    }

    buf1 -= shift; buf2 -= shift;
    free(buf1); free(buf2);
}

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

    cin >> n;
    edges.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b; a--; b--;
        ll c; cin >> c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }

    set_parent(0, -1);
    calc(0);
    cout << DP[0][0] << '\n';
}