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>
using namespace std;
using ll = long long;
const int MAXN = 200005;
int n, a, b, w;
vector<pair<int, int>> g[MAXN];
ll poprawne[200005][6];

void dfs(int v, int parent) {
    for (auto u : g[v]) {
        if(u.first == parent) continue;
        dfs(u.first, v);
    }

    //cout << v << endl;
    int deg = (g[v].size() - (v != parent)) / 2 + 1;
    vector<ll> dp[2][2];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            dp[i][j] = vector<ll>(2 * deg + 4, -1e18);

    // cur, parzystosc, roznica
    dp[0][0][0 + deg + 2] = 0;
    
    int cur = 0;

    for (auto u : g[v]) {
        if(u.first == parent) continue;
        cur = 1 - cur;

        for (int roznica = -deg; roznica <= deg; roznica++) {
            for (int par = 0; par < 2; par++) {
                // ujemne indeksy :(
                int roz = roznica + deg + 2;
                // Syn nie robił ścieżki do ojca
                dp[cur][par][roz] = max(dp[cur][par][roz], dp[1 - cur][par][roz] + poprawne[u.first][0]);
                    
                // Syn stworzył ścieżkę długości 1
                dp[cur][par][roz] = max(dp[cur][par][roz], dp[1 - cur][par][roz - 1] + poprawne[u.first][1] + u.second);

                // Syn stworzył ścieżkę długości 2
                dp[cur][par][roz] = max(dp[cur][par][roz], dp[1 - cur][1 - par][roz] + poprawne[u.first][2] + u.second);

                // Syn stworzył ścieżkę długości 3
                dp[cur][par][roz] = max(dp[cur][par][roz], dp[1 - cur][par][roz + 1] + poprawne[u.first][3] + u.second);


                // Syn stworzył ścieżkę długości 4
                dp[cur][par][roz] = max(dp[cur][par][roz], dp[1 - cur][par][roz] + poprawne[u.first][4] + u.second);
            }
        }
    }

    // Poprawne rozwiązania to takie, że ile1=ile3 i ile2 jest parzyste

    for (int i = 2; i <= 4; i++) poprawne[v][i] = -1e18;

    poprawne[v][0] = poprawne[v][1] = dp[cur][0][deg + 2];
    poprawne[v][2] = dp[cur][0][1 + deg + 2];
    poprawne[v][3] = dp[cur][1][0 + deg + 2];
    poprawne[v][4] = dp[cur][0][-1 + deg + 2];
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

    dfs(1, 0);
    cout << poprawne[1][0] << "\n";
}