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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int max_data = 2e5;
const long long oo = 1e15;

vector<int> neighbour[max_data];
vector<int> weight[max_data];
long long S[max_data][4];

long long maximum(long long a, long long b, long long c, long long d, long long e)
{
//printf("maximum: %lld %lld %lld %lld %lld\n", a, b, c, d, e);
    long long max = a;
    if (b > max) max = b;
    if (c > max) max = c;
    if (d > max) max = d;
    if (e > max) max = e;
    return max;
}

void bfs(int vertex, int parent = -1)
{
    int index = 0;
    static long long wynik[2][max_data][2];
    int el = neighbour[vertex].size()+4;
    
    for (int i = 0; i < neighbour[vertex].size(); i++)
        if (neighbour[vertex][i] != parent)
            bfs(neighbour[vertex][i], vertex);
    
    for (int i = 0; i < el; i++)
        wynik[0][i][0] = wynik[1][i][0] = wynik[0][i][1] = wynik[1][i][1] = -oo;
    wynik[0][el/2][index] = 0;
    
    for (int i = 0; i < neighbour[vertex].size(); i++)
    {
        int n = neighbour[vertex][i];
        int w = weight[vertex][i];
        
        if (n != parent)
        {
            index = 1-index;
            
            for (int par = 0; par < 2; par++)
            {
                for (int j = 1; j < el-1; j++)
                {
                    wynik[par][j][index] = maximum(S[n][0] +     wynik[par]   [j] [1-index],
                                                   S[n][0] + w + wynik[par]  [j-1][1-index],
                                                   S[n][1] + w + wynik[1-par] [j] [1-index],
                                                   S[n][2] + w + wynik[par]  [j+1][1-index],
                                                   S[n][3] + w + wynik[par]   [j] [1-index]);
                    //printf("wynik[%d][%d][%d] = %lld\n", par, j, index, wynik[par][j][index]);
                }
            }
        }
    }
    
    S[vertex][0] = wynik[0] [el/2] [index];
    S[vertex][1] = wynik[0][el/2+1][index];
    S[vertex][2] = wynik[1] [el/2] [index];
    S[vertex][3] = wynik[0][el/2-1][index];
    /*printf("el: %d\n", el);
    printf("%d: ", vertex+1);
    for (int i = 0; i < 4; i++)
        printf("%lld ", S[vertex][i]);
    printf("\n\n");*/
}

int main()
{
    int n;
    
    scanf("%d", &n);
    
    for (int i = 1; i < n; i++)
    {
        int u, v, z;
        
        scanf("%d%d%d", &u, &v, &z);
        
        u--;
        v--;
        
        neighbour[u].push_back(v);
        neighbour[v].push_back(u);
        weight[u].push_back(z);
        weight[v].push_back(z);
    }
    
    bfs(0, -1);
    
    printf("%lld\n", S[0][0]);
    
    return 0;
}