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
#include "bits/stdc++.h" // Ignacy Boehlke
using namespace std;     // XIII LO Szczecin
template<class A, class B> ostream& operator << (ostream& os, const pair<A, B>& p) {return os << '{' << p.first << ", " << p.second << '}';}
template<class T> auto operator << (ostream& os, const T& v) -> decltype(v.begin(), os) {os << '{';for (auto i : v) os << i << ", ";return os << '}';}
#ifdef DEBUG
#define D(x...) x
#else
#define D(x...)
#endif
#define LN(x) D(cerr << #x << ": " << x << ' ')
#define LOG(x) D(cerr << #x << ": " << x << '\n')
#define ssize(x) ((int)x.size())
#define FOR(a, b, c) for(int a = (b); a <= (c); ++a)
#define REP(a, b) FOR(a, 0, b - 1)
#define ALL(x) (x).begin(), (x).end()
#define fi first
#define se second
using ll = long long;

vector<vector<pair<int, int>>> graph;
vector<array<ll, 4>> dp;

void dfs(int v, int p) {
    REP(i, ssize(graph[v])) if (graph[v][i].fi == p) {
        swap(graph[v][i], graph[v][ssize(graph[v]) - 1]);
        graph[v].pop_back();
    }
    int c = ssize(graph[v]);
    if (!c) return;
    for (const auto& [u, w] : graph[v]) dfs(u, v);
    LOG(v);
    vector<array<ll, 4>> nums(c);
    REP(i, c) {
        REP(j, 4) nums[i][j] = dp[graph[v][i].fi][(j ? j - 1 : 3)] + graph[v][i].se;
        nums[i][0] = max(nums[i][0], dp[graph[v][i].fi][0]);
    }
    LOG(nums);
    vector dp2(2, vector<vector<ll>>(2, vector<ll>(2 * c + 2, -(ll)1e18)));
    dp2[0][0][c + 1] = nums[0][0];
    dp2[0][0][c] = nums[0][1];
    dp2[0][1][c + 1] = nums[0][2];
    dp2[0][0][c + 2] = nums[0][3];
    bool s = false;
    FOR(i, 1, c - 1) {
        s = !s;
        REP(j, 2) {
            FOR(k, 1, 2 * c) {
                dp2[s][j][k] = max({dp2[!s][j][k] +     nums[i][0],
                                    dp2[!s][j][k + 1] + nums[i][1],
                                    dp2[!s][!j][k] +    nums[i][2],
                                    dp2[!s][j][k - 1] + nums[i][3]});
            }
        }
    }
    dp[v][0] = dp2[s][0][c + 1];
    dp[v][1] = dp2[s][0][c];
    dp[v][2] = dp2[s][1][c + 1];
    dp[v][3] = dp2[s][0][c + 2];
    LOG(dp[v]);
}

int main() {
    int n;
    scanf("%d", &n);
    graph.resize(n);
    dp.resize(n, {0, -(ll)1e18, -(ll)1e18, -(ll)1e18});
    REP(i, n - 1) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w); --a; --b;
        graph[a].emplace_back(b, w);
        graph[b].emplace_back(a, w);
    }
    dfs(0, 0);
    printf("%lld\n", dp[0][0]);
}