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
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAKS 200010
#define INF 1000000000000000000LL
#define INTINF 2000000000
#define mp make_pair
using namespace std;
typedef pair<int,int> para;
typedef long long int lld;
vector<para> sas[MAKS];
bool bylo[MAKS];
lld f[MAKS][4];

lld g[2][MAKS][2];

inline lld lepszy(lld kand, lld poprz, lld fw, lld wart)
{
    if(poprz==-INF || fw==-INF)return kand;
    return max(kand,poprz+fw+wart);
}

void licz(int v)
{
    //printf("v: %d\n",v);
    bylo[v]=true;
    for(int i=0;i<sas[v].size();i++)
    {
        if(bylo[sas[v][i].first])
        {
            sas[v][i].second = -INTINF;
            continue;
        }
        licz(sas[v][i].first);
    }

    for(int q=0;q<4;q++)
    {
        // f[v][q]
        //printf("f(%d, %d) START\n",v, q);
        int akt=0;
        int n=0;
        for(int i=0;i<sas[v].size();i++)
        {
            if(sas[v][i].second!=-INTINF)n++;
        }
        int pol=n/2+1;
        //printf("n: %d, pol: %d\n", n, pol);

        // sztuczne poprzednie
        for(int balans=-pol;balans<=pol;balans++)
        {
            for(int parz=0;parz<2;parz++)
            {
                if(balans==0 && parz)g[akt][balans+pol][parz]=0;
                else g[akt][balans+pol][parz]=-INF;
            }
        }

        // właściwe
        for(int i=0;i<sas[v].size();i++)
        {
            int u=sas[v][i].first; lld wart=sas[v][i].second;
            if(wart==-INTINF)continue;

            int poprz=akt;
            akt=1-akt;
            //printf("u: %d (%lld)\n", u, wart);
            //printf("fu: %lld %lld %lld %lld\n",f[u][0],f[u][1],f[u][2],f[u][3]);
            for(int balans=-pol;balans<=pol;balans++)
            {
                for(int parz=0;parz<2;parz++)
                {
                    // g[i*][balans+pol][parz]

                    // pojedynczo
                    lld kand=lepszy(-INF, g[poprz][balans+pol][parz], f[u][0], 0LL);
                    //printf("kand: %lld\n", kand);
                    kand=lepszy(kand, g[poprz][balans+pol][parz], f[u][3], wart);
                    //printf("kand: %lld\n", kand);

                    // parujemy przez f1
                    kand = lepszy(kand, g[poprz][balans+pol][1-parz], f[u][1], wart);
                    //printf("kand: %lld\n", kand);

                    // parujemy przez f0 lub f2
                    if((balans-1) >= -pol) kand=lepszy(kand, g[poprz][balans-1+pol][parz], f[u][0], wart);
                    //printf("kand: %lld\n", kand);
                    if((balans+1) <=  pol) kand=lepszy(kand, g[poprz][balans+1+pol][parz], f[u][2], wart);
                    //printf("kand: %lld\n", kand);

                    g[akt][balans+pol][parz]=kand;
                    //printf("g(%d, %d, %d) = %lld\n",i, balans, parz, kand);
                }
            }
        }
        switch(q)
        {
            case 0:
                f[v][q]=g[akt][0+pol][1];
                f[v][q]=max(f[v][q], 0LL);
                break;
            case 1:
                f[v][q]=g[akt][1+pol][1];
                break;
            case 2:
                f[v][q]=g[akt][0+pol][0];
                break;
            case 3:
                f[v][q]=g[akt][(-1)+pol][1];
                break;
        }

        //printf("f(%d, %d) = %lld\n",v, q, f[v][q]);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        sas[a].push_back(mp(b,c));
        sas[b].push_back(mp(a,c));
    }
    licz(1);
    printf("%lld\n",f[1][0]);
}