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
#define make_pair mp
#define emplace_back pb
#include <bits/stdc++.h>
using namespace std;
mt19937 mt_rand(time(0));
const int N = 2e5 + 5;
const long long INF = -5e17;
long long dp[N][4], sum[N][2][2], kak[N];
int n, par[N];
vector<int> v[N], w[N];

void dfs(int x) {
    for(int j=0;j<v[x].size();j++) {
        int y = v[x][j];
        long long c = w[x][j];
        if(par[x] != y) {
            par[y] = x;
            dfs(y);
            kak[y] = max(dp[y][0], c + dp[y][3]);
        }
    }

    if(x != 1 && v[x].size() == 1) {
        for(int i=1;i<4;i++) dp[x][i] = INF;
        dp[x][0] = 0;
        kak[x] = 0;
        return;
    }

    int m = v[x].size();
    int mm = m;
    if(x != 1) mm--;
    for(int i=0;i<=mm;i++) {
        sum[i][0][0] = INF;
        sum[i][1][0] = INF;
    }
    sum[0][0][0] = 0;
    long long s = 0;
    for(int j=0;j<m;j++) {
        int y = v[x][j];
        long long c = w[x][j];
        if(y != par[x]) s += c + dp[y][0];
    }

    for(int j=0;j<m;j++) {
        int y = v[x][j];
        long long c = w[x][j];
        if(par[x] == y) continue;
        for(int i=mm;i>=0;i--) {
            if(i > 1) {
                sum[i][0][0] = max(sum[i][0][0], sum[i-2][0][0] + dp[y][2] - dp[y][0]);
                sum[i][1][0] = max(sum[i][1][0], sum[i-2][1][0] + dp[y][2] - dp[y][0]);
            }
            if(i > 0) {
                sum[i][0][0] = max(sum[i][0][0], sum[i-1][0][0] + kak[y] - c - dp[y][0]);
                sum[i][1][0] = max(sum[i][1][0], sum[i-1][1][0] + kak[y] - c - dp[y][0]);
                sum[i][0][0] = max(sum[i][0][0], sum[i-1][1][0] + dp[y][1] - dp[y][0]);
                sum[i][1][0] = max(sum[i][1][0], sum[i-1][0][0] + dp[y][1] - dp[y][0]);
            }
        }
    }
    dp[x][0] = s + sum[mm][0][0];

    for(int i2=1;i2<4;i2++) {
        for(int i=0;i<=mm;i++) {
            sum[i][0][0] = INF;
            sum[i][1][0] = INF;
            sum[i][0][1] = INF;
            sum[i][1][1] = INF;
        }
        sum[0][0][0] = 0;
        for(int j=0;j<m;j++) {
            int y = v[x][j];
            long long c = w[x][j];
            if(par[x] == y) continue;
            for(int i=mm;i>=0;i--) {
                if(i > 1) {
                    sum[i][0][0] = max(sum[i][0][0], sum[i-2][0][0] + dp[y][2] - dp[y][0]);
                    sum[i][1][0] = max(sum[i][1][0], sum[i-2][1][0] + dp[y][2] - dp[y][0]);
                    sum[i][0][1] = max(sum[i][0][1], sum[i-2][0][1] + dp[y][2] - dp[y][0]);
                    sum[i][1][1] = max(sum[i][1][1], sum[i-2][1][1] + dp[y][2] - dp[y][0]);
                }
                if(i > 0) {
                    sum[i][0][0] = max(sum[i][0][0], sum[i-1][0][0] + kak[y] - c - dp[y][0]);
                    sum[i][1][0] = max(sum[i][1][0], sum[i-1][1][0] + kak[y] - c - dp[y][0]);
                    sum[i][0][1] = max(sum[i][0][1], sum[i-1][0][1] + kak[y] - c - dp[y][0]);
                    sum[i][1][1] = max(sum[i][1][1], sum[i-1][1][1] + kak[y] - c - dp[y][0]);
                    sum[i][0][1] = max(sum[i][0][1], sum[i-1][0][0] + dp[y][i2-1] - dp[y][0]);
                    sum[i][1][1] = max(sum[i][1][1], sum[i-1][1][0] + dp[y][i2-1] - dp[y][0]);
                    sum[i][1][1] = max(sum[i][1][1], sum[i-1][0][1] + dp[y][1] - dp[y][0]);
                    sum[i][0][0] = max(sum[i][0][0], sum[i-1][1][0] + dp[y][1] - dp[y][0]);
                    sum[i][1][0] = max(sum[i][1][0], sum[i-1][0][0] + dp[y][1] - dp[y][0]);
                    sum[i][0][1] = max(sum[i][0][1], sum[i-1][1][1] + dp[y][1] - dp[y][0]);
                }
            }
        }
        dp[x][i2] = s + sum[mm][0][1];
    }
}
int main() {
	scanf("%d", &n);
    for(int i=1;i<n;i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        v[a].pb(b);
        v[b].pb(a);
        w[a].pb(c);
        w[b].pb(c);
    }
    dfs(1);
    /*printf("\n");
    for(int i=1;i<=n;i++) {
        printf("%d\n", i);
        printf("%lld %lld %lld %lld\n", dp[i][0], dp[i][1], dp[i][2], dp[i][3]);
    }*/
    printf("%lld\n", dp[1][0]);
	return 0;
}