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 <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>

using namespace std;

const int MAXN = 200005;
const long long INF = 1e18;
const int LIM = 1500;

int n, odw[MAXN];
vector<pair<int, int>> v[MAXN];
long long w[MAXN][4];
long long tmp[4][2 * LIM + 1];

struct sasiad {
    long long x[3];
    sasiad(long long *t) {
        x[0] = t[0];
        x[1] = t[1];
        x[2] = t[2];
    }
};

void dfs(int a) {
    w[a][0] = 0;
    w[a][1] = w[a][2] = w[a][3] = -INF;
    
    odw[a] = 1;
    long long bonus = 0;
    vector<sasiad> xd;
    
    for (const auto &p : v[a]) {
        int s = p.first;
        if (!odw[s]) {
            dfs(s);
            long long tmpd = w[s][3];
            /*if (a==2 && s == 5) {
                for (int i = 0; i < 4; i++) cerr << w[s][i] << ' ';
                cerr<<endl;
            }*/
            for (int i = 3; i > 0; i--) w[s][i] = w[s][i-1] + p.second;
            w[s][0] = max(tmpd + p.second, w[s][0]);
            /*if (a==2 && s == 5) {
                for (int i = 0; i < 4; i++) cerr << w[s][i] << ' ';
                cerr<<endl;
            }*/
            
            if (w[s][0] > 0) {
                bonus += w[s][0];
                for (int i = 1; i < 4; i++) w[s][i] -= w[s][0];
            }
            xd.emplace_back(w[s] + 1);
        }
    }
    
    random_shuffle(xd.begin(), xd.end());
    fill(tmp[0], tmp[0] + 2*LIM + 1, -INF);
    fill(tmp[1], tmp[1] + 2*LIM + 1, -INF);
    tmp[0][LIM] = 0;
    int right = LIM, left = LIM;
    
    for (const sasiad &s: xd) {
        copy_n(tmp[0] + left, right - left + 1, tmp[2] + left);
        copy_n(tmp[1] + left, right - left + 1, tmp[3] + left);
        for (int i = max(1, left) - 1; i < right; i++) {
            tmp[0][i] = max(tmp[0][i], tmp[2][i+1] + s.x[0]);
            tmp[1][i] = max(tmp[1][i], tmp[3][i+1] + s.x[0]);
        }
        for (int i = min(2*LIM, right+1); i > left; i--) {
            tmp[0][i] = max(tmp[0][i], tmp[2][i-1] + s.x[2]);
            tmp[1][i] = max(tmp[1][i], tmp[3][i-1] + s.x[2]);
        }
        for (int i = left; i <= right; i++) {
            tmp[0][i] = max(tmp[0][i], tmp[3][i] + s.x[1]);
            tmp[1][i] = max(tmp[1][i], tmp[2][i] + s.x[1]);
        }
        if (left > 0) left--;
        if (right < 2*LIM) right++;
    }
    
    w[a][0] = tmp[0][LIM] + bonus;
    w[a][2] = tmp[1][LIM] + bonus;
    
    w[a][1] = tmp[0][LIM - 1] + bonus;
    w[a][3] = tmp[0][LIM + 1] + bonus;
    //if (a == 5) cerr << w[a][2] << endl;
    
    //cerr << a << ' '<< w[a][0] << ' ' << w[a][1] << ' ' << w[a][2] << ' ' << w[a][3] << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].emplace_back(b, c);
        v[b].emplace_back(a, c);
    }
    
    dfs(1);
    cout << w[1][0] << endl;
}