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
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 200'007;
vector<pair<int, int>>adj[MAX_N];
const long long inf = 1'000'000'000'000'000'000;
long long dp[MAX_N][4];
int n;

void DFS(int x, pair<int, int>p) {
    if(find(adj[x].begin(), adj[x].end(), p) != adj[x].end())
        adj[x].erase(find(adj[x].begin(), adj[x].end(), p));
    fill(dp[x], dp[x] + 4, -inf);
    dp[x][0] = 0;
    int n = adj[x].size();
    if(n == 0)
        return;
    
    for(pair<int, int>p : adj[x])
        DFS(p.first, make_pair(x, p.second));
    
    vector<vector<vector<vector<long long>>>>DP(2, vector<vector<vector<long long>>>(n + 1, vector<vector<long long>>(n + 3, vector<long long>(2, -inf))));
    
    for(int t = 0; t < 2; t++) {
        DP[t][0][n / 2][0] = 0;
        for(int i = 0; i < n; i++) {
            int y = adj[x][i].first, w = adj[x][i].second;
            for(int j = 0; j < n + 3; j++) {
                for(int k = 0; k < 2; k++) {
                    //idle 0 or 3
                    DP[t][i + 1][j][k] = max(DP[t][i + 1][j][k], DP[t][i][j][k] + max(dp[y][3] + w, dp[y][0]));
                    //active 1
                    DP[t][i + 1][j][k ^ 1] = max(DP[t][i + 1][j][k ^ 1], DP[t][i][j][k] + dp[y][1] + w);
                    //active 0
                    if(j > 0)
                        DP[t][i + 1][j - 1][k] = max(DP[t][i + 1][j - 1][k], DP[t][i][j][k] + dp[y][0] + w);
                    //active 2
                    if(j <= n + 1)
                        DP[t][i + 1][j + 1][k] = max(DP[t][i + 1][j + 1][k], DP[t][i][j][k] + dp[y][2] + w);
                }
            }
        }
        
        reverse(adj[x].begin(), adj[x].end());
    }

    for(int chosen = 0; chosen < n; chosen++) {
        int l = chosen, r =  n - chosen - 1;
        long long bestValue = -inf;
        for(int left = - n / 2; left <= n / 2; left++) {
            for(int k = 0; k < 2; k++) {
                bestValue = max(bestValue, DP[0][l][n / 2 + left][k] + DP[1][r][n / 2 - left][k]);
            }
        }
        int y = adj[x][chosen].first, w = adj[x][chosen].second;
        for(int i = 1; i < 4; i++) {
            dp[x][i] = max(dp[x][i], bestValue + dp[y][i - 1] + w);
        }
    }
    dp[x][0] = DP[0][n][n / 2][0];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i < n; i++) {
        int x, y, w; cin >> x >> y >> w;
        adj[x - 1].emplace_back(y - 1, w);
        adj[y - 1].emplace_back(x - 1, w);
    }
    
    DFS(0, {-1, -1});
    
    cout << dp[0][0] << '\n';
    
    return 0;
}