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 <queue>
#include <algorithm>

using namespace std;

struct Vertex{
    long long Max[4];
    int d;
    vector<int> D;
    vector<long long> C;
    bool doBfs;
};

vector<int> ww;
long long INF;
Vertex V[200000];
long long tab[100000][4];
long long dp[2][200000][2];

void Bfs(int N) {
    queue<int> Q;
    Q.push(N);
    V[N].doBfs = true;
    while(!Q.empty()) {
        int w = Q.front();
        int p = V[w].D.size();
        int usun = -1;
        for(int i=0; i<p; ++i) {
            if(!V[V[w].D[i]].doBfs) {
                Q.push(V[w].D[i]);
                V[V[w].D[i]].doBfs = true;
            }
            else {
                usun = i;
            }
        }
        if(usun != -1) {
            V[w].D.erase(V[w].D.begin() + usun);
            V[w].C.erase(V[w].C.begin() + usun);
        }
        ww.push_back(Q.front());
        Q.pop();
    }
}

int main() {
    INF = 1 << 30;
    INF = INF*INF;
    int c = 100000;
    int n;
    cin>>n;
    for(int i=0; i<n-1; ++i) {
        int u,v,z;
        cin>>u>>v>>z;
        V[u-1].D.push_back(v-1);
        V[v-1].D.push_back(u-1);
        V[u-1].C.push_back(z);
        V[v-1].C.push_back(z);
    }
    for(int i=0; i<n; ++i) V[i].doBfs = false;
    Bfs(0);
    reverse(ww.begin(),ww.end());
    for(int i=0; i<ww.size(); ++i) {
        if(V[ww[i]].D.size() == 0) {
            V[ww[i]].Max[0] = 0;
            V[ww[i]].Max[1] = V[ww[i]].Max[2] = V[ww[i]].Max[3] = - INF;
        }
        else {
            int H = V[ww[i]].D.size();
            for(int j=0; j<H; ++j) {
                tab[j][0] = max(V[V[ww[i]].D[j]].Max[0],V[V[ww[i]].D[j]].Max[3] + V[ww[i]].C[j]);
                for(int k=1; k<4; ++k) {
                    tab[j][k] = V[V[ww[i]].D[j]].Max[k-1] + V[ww[i]].C[j];
                }
            }
            for(int j=0; j<H; ++j)
            for(int j=0; j<200000; ++j) {
                dp[0][j][0] = dp[0][j][1] = -INF;
            }
            dp[0][c][0] = tab[0][0];
            dp[0][c][1] = tab[0][2];
            dp[0][c+1][0] = tab[0][1];
            dp[0][c-1][0] = tab[0][3];
            for(int k=1; k<H; ++k) {
                for(int j=c-H; j<=c+H; ++j)
                for(int b=0; b<2; ++b) {
                    dp[1][j][b] = max( max(dp[0][j-1][b] + tab[k][1], dp[0][j+1][b] + tab[k][3]), max(dp[0][j][!b] + tab[k][2], dp[0][j][b] + tab[k][0]));
                }
                for(int j=c-H; j<=c+H; ++j)
                for(int b=0; b<2; ++b) {
                    dp[0][j][b] = dp[1][j][b];
                }
            }
            V[ww[i]].Max[0] = dp[0][c][0];
            V[ww[i]].Max[1] = dp[0][c+1][0];
            V[ww[i]].Max[2] = dp[0][c][1];
            V[ww[i]].Max[3] = dp[0][c-1][0];
        }
    }
    cout<<V[0].Max[0]<<endl;
    
    
    
    
    return 0;
}