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
132
133
134
135
136
137
#include <bits/stdc++.h>
const long long mininf = -100000000000000000;
using namespace std;

vector<pair<int, int>> sc[200005];

struct res
{
    long long w[4]{};
    void init(long long a = mininf, long long b = mininf, long long c = mininf, long long d = mininf)
    {
        w[0] = a;
        w[1] = b;
        w[2] = c;
        w[3] = d;
    }
    void addV(long long v)
    {
        for (int i = 0; i < 4; i++)
            w[i] += v;
        for (int i = 2; i >= 0; i--)
            swap(w[i], w[i + 1]);
        w[0] = max(w[0], w[1] - v);
        w[1] = max(w[1], v);
    }
};

long long dp[400015][2][2];

res dfs(int w, int f)
{
    // cout << w << '\n'
    vector<res> v;
    res retv;
    retv.init();
    if (sc[w].size() == 1 && f != 0)
        return retv;
    for (auto i : sc[w])
    {
        if (i.first == f)
            continue;
        res tm = dfs(i.first, w);
        tm.addV(i.second);
        v.push_back(tm);
    }
    int k = v.size();
    for (int i = 0; i <= k * 2 + 10; i++)
    {
        dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = dp[i][1][1] = mininf;
    }
    // cout << k << '\n'
        //  << flush;
    dp[k][0][0] = 0;
    dp[k][0][1] = 0;
    int s = 0;
    for (auto i : v)
    {
        s ^= 1;
        // cout << "S: " << i.w[0] << ' ' << i.w[1] << ' ' << i.w[2] << ' ' << i.w[3] << ' ' << w << '\n'
            //  << flush;
        for (int a = 0; a < 2; a++)
        {
            for (int b = -k; b <= k; b++)
                dp[b + k][a][s] = dp[b + k][a][s ^ 1];
        }

        for (int a = 0; a < 2; a++)
        {
            // cout << "A: " << a << ' ';
            for (int b = -k; b <= k; b++)
            {
                dp[k + b][a][s] = max(dp[k + b][a][s], dp[k + b][a][s ^ 1] + i.w[0]);
                dp[k + b][a][s] = max(dp[k + b][a][s], dp[k + b][a ^ 1][s ^ 1] + i.w[2]);
                dp[k + b + 1][a][s] = max(dp[k + b + 1][a][s], dp[k + b][a][s ^ 1] + i.w[1]);
                dp[k + b][a][s] = max(dp[k + b][a][s], dp[k + b + 1][a][s ^ 1] + i.w[3]);
                // cout << dp[k + b][a][s] << ' ';
            }
            // cout << '\n';
        }
    }
    retv.init(dp[k][0][s], dp[k + 1][0][s], dp[k][1][s], dp[k - 1][0][s]);
    // for (int i = 0; i < (1 << (v.size() * 2)); i++)
    // {
    //     bool ps = 1;
    //     long long sm = 0;
    //     res x;
    //     for (int j = 0; j < v.size(); j++)
    //     {
    //         int sj = ((i & (1 << (j * 2))) >= 1) + 2 * ((i & (1 << (j * 2 + 1))) >= 1);
    //         // cout << sj << ' ' << v[j].w[sj] << '\t';
    //         x.w[sj]++;
    //         if (v[j].w[sj] == mininf)
    //             ps = 0;
    //         sm += v[j].w[sj];
    //     }
    //     if (!ps)
    //         continue;
    //     if (x.w[2] % 2)
    //     {
    //         if (x.w[1] != x.w[3])
    //             continue;
    //         retv.w[2] = max(retv.w[2], sm);
    //     }
    //     else
    //     {
    //         if (x.w[1] == x.w[3])
    //             retv.w[0] = max(retv.w[0], sm);
    //         if (x.w[1] == x.w[3] + 1)
    //             retv.w[1] = max(retv.w[1], sm);
    //         if (x.w[1] + 1 == x.w[3])
    //             retv.w[3] = max(retv.w[3], sm);
    //     }
    //     // cout << '\n';
    // }
    // cout<<w<<' '<<retv.w[0]<<' '<<retv.w[1]<<' '<<retv.w[2]<<' '<<retv.w[3]<<'\n';
    return retv;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        sc[a].push_back({b, c});
        sc[b].push_back({a, c});
    }
    int mxs = 0;
    for (int i = 1; i <= n; i++)
    {
        mxs = max(mxs, (int)sc[i].size());
    }
    cout << max(dfs(1, 0).w[0], (long long)0);
}