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


using ll = long long int;
using namespace std;

const int MAXN = 200010;
const int MAXK = 1500;
const ll INF = (ll)MAXN * 1000000000LL;


vector<pair<int, ll>> graph[MAXN];
ll DP[MAXN][4];
ll dph[2 * MAXK + 10][2][2];


void DFS(int v, int prevv) {

  vector<pair<int, ll>> sons;
  for (auto [b, w] : graph[v]) {
    if (b != prevv) {
      sons.push_back({ b, w });
      DFS(b, v);
    }
  }
  random_shuffle(sons.begin(), sons.end());
  int sonc = sons.size();

  // Leaf node
  if (sonc == 0) {
    DP[v][0] = 0;
    DP[v][1] = -INF;
    DP[v][2] = -INF;
    DP[v][3] = -INF;
    return;
  }


  int off = min(sonc + 2, MAXK);
  for (int k = 0; k <= 2 * off; k++) {
    dph[k][0][1] = -INF;
    dph[k][1][1] = -INF;
    dph[k][0][0] = -INF;
    dph[k][1][0] = -INF;
  }
  dph[off][0][1] = 0;



  for (int i = 0; i < sonc; i++) {
    int ii = i & 1;
    for (int k = 1; k < 2 * off; k++) {
      for (int r = 0; r < 2; r++) {
        dph[k][r][ii] = max(
          max(
            dph[k][r][ii ^ 1] + max(DP[sons[i].first][0], DP[sons[i].first][3] + sons[i].second),
            dph[k][r ^ 1][ii ^ 1] + sons[i].second + DP[sons[i].first][1]
          ),
          max(
            dph[k + 1][r][ii ^ 1] + sons[i].second + DP[sons[i].first][0],
            dph[k - 1][r][ii ^ 1] + sons[i].second + DP[sons[i].first][2]
          )
        );
      }
    }
  }

  DP[v][0] = dph[off][0][(sonc & 1) ^ 1];
  DP[v][1] = dph[off - 1][0][(sonc & 1) ^ 1];
  DP[v][2] = dph[off][1][(sonc & 1) ^ 1];
  DP[v][3] = dph[off + 1][0][(sonc & 1) ^ 1];
}


int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int a, b;
    ll x;
    scanf("%d%d%lld", &a, &b, &x);

    graph[a].push_back({ b, x });
    graph[b].push_back({ a, x });
  }
  srand(n * (int)graph[1][0].second);

  DFS(1, 1);
  printf("%lld\n", DP[1][0]);
}