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
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX_N 200010
#define MAX_D 800
#define OFFSET (MAX_D + 3)
#define BAD -1000000000000000000ll
using namespace std;

long long best[MAX_N][4];
long long dp1[2][2 * MAX_D + 10], dp2[2][2 * MAX_D + 10];

vector<pair<int, int> > v[MAX_N];

inline long long max6(long long a, long long b, long long c, long long d, long long e, long long f) {
    return max(max(max(a, b), max(c, d)), max(e, f));
}

void update_best(int w, int edge_cost) {
    long long best0 = max(best[w][0], best[w][3] + edge_cost);
    long long best1 = best[w][0] + edge_cost;
    long long best2 = best[w][1] + edge_cost;
    long long best3 = best[w][2] + edge_cost;
    best[w][0] = best0;
    best[w][1] = best1;
    best[w][2] = best2;
    best[w][3] = best3;
}

void dfs(int w, int par) {
    vector<int> perm;

    for (int i = 0; i < (int)v[w].size(); i++) {
        if (v[w][i].first == par) continue;

        dfs(v[w][i].first, w);
        update_best(v[w][i].first, v[w][i].second);

        perm.push_back(v[w][i].first);
    }

    random_shuffle(perm.begin(), perm.end());

    int max_d = min((long long)MAX_D, (long long)(perm.size() + 3));

    for(int i = -max_d; i <= max_d; i++) {
        dp1[0][i + OFFSET] = BAD;
        dp1[1][i + OFFSET] = BAD;
    }

    dp1[0][0 + OFFSET] = 0;

    for (int i = 0; i < (int)perm.size(); i++) {
        // last: dp1 new: dp2
        // ilosc jedynek minus ilosc trójek
        auto B = best[perm[i]];

        for (int d = -max_d; d <= max_d; d++) {
            dp2[0][d + OFFSET] = max6(
                    BAD,
                    dp1[0][d + OFFSET],
                    dp1[0][d + OFFSET] + B[0],
                    d > -max_d ? (dp1[0][d - 1 + OFFSET] + B[1]) : BAD,
                    dp1[1][d + OFFSET] + B[2],
                    d < max_d ? (dp1[0][d + 1 + OFFSET] + B[3]) : BAD
            );
            dp2[1][d + OFFSET] =  max6(
                    BAD,
                    dp1[1][d + OFFSET],
                    dp1[1][d + OFFSET] + B[0],
                    d > -max_d ? (dp1[1][d - 1 + OFFSET] + B[1]) : BAD,
                    dp1[0][d + OFFSET] + B[2],
                    d < max_d ? (dp1[1][d + 1 + OFFSET] + B[3]) : BAD
            );
        }
        swap(dp1, dp2);
    }

    best[w][0] = dp1[0][0 + OFFSET];
    best[w][1] = dp1[0][1 + OFFSET];
    best[w][2] = dp1[1][0 + OFFSET];
    best[w][3] = dp1[0][-1 + OFFSET];
    //printf("\n\n%d:\n", w);
    //for (int i = 0; i < 4; i++) {
    //    printf("%d: %lld\n", i, best[w][i]);
    //}

}

int main() {
    int n;
    scanf("%d", &n);
    //n = 200000;
    for (int i = 1; i < n; i++) {
        int v1, v2, c;

        scanf("%d%d%d", &v1, &v2, &c);
        //v1 = 1;
        //v2 = i + 1;
        //c = 5;

        v[v1].emplace_back(v2, c);
        v[v2].emplace_back(v1, c);
    }

    dfs(1, -1);

    printf("%lld\n", best[1][0]);
}