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
#include <bits/stdc++.h>
using namespace std;

const int64_t INFTY = 1e18;
typedef array<int64_t, 4> T;

vector<vector<pair<int, int>>> graph;
int64_t DP[2][4 * (int)1e5 + 1][2];

T dfs(int u, int parent) {
  vector<T> children;
  for (auto edge : graph[u]) {
    if (edge.first != parent) {
      T result = dfs(edge.first, u);
      T result_plus_edge;
      result_plus_edge[0] = max(result[0], result[3] + edge.second);
      for (int i = 1; i <= 3; ++i)
        result_plus_edge[i] = result[i - 1] + edge.second;
      children.push_back(result_plus_edge);
    }
  }

  random_shuffle(children.begin(), children.end());
  int max_delta = max(1, (int)children.size());
  max_delta = 50 + 4 * sqrt(max_delta);

  for (int d = -max_delta; d <= max_delta; ++d)
    for (int b = 0; b < 2; ++b)
      DP[0][d + max_delta][b] = -INFTY;
  DP[0][0 + max_delta][0] = 0;

  int cur = 0, prv = 1;
  for (T child : children) {
    swap(cur, prv);
    for (int d = -max_delta; d <= max_delta; ++d) {
      for (int b = 0; b < 2; ++b) {
        int64_t best = max(
          DP[prv][d + max_delta][b] + child[0],
          DP[prv][d + max_delta][1 - b] + child[2]);
        if (d != -max_delta)
          best = max(best, DP[prv][d + max_delta - 1][b] + child[1]);
        if (d != max_delta)
          best = max(best, DP[prv][d + max_delta + 1][b] + child[3]);
        DP[cur][d + max_delta][b] = best;
      }
    }
  }

  T outcome;
  outcome[0] = DP[cur][0 + max_delta][0];
  outcome[1] = DP[cur][1 + max_delta][0];
  outcome[2] = DP[cur][0 + max_delta][1];
  outcome[3] = DP[cur][-1 + max_delta][0];

  // cerr << "dfs(" << u << ", " << parent << ") = " << outcome[0] << ", " << outcome[1] << ", " << outcome[2] << ", " << outcome[3] << endl;

  return outcome;
}

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  graph.resize(n);
  for (int i=0; i<n-1; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    graph[a].emplace_back(b, c);
    graph[b].emplace_back(a, c);
  }
  // int max_deg = 0;
  // for (int i = 0; i < n; ++i)
  //   max_deg = max(max_deg, (int)graph[i].size());
  // cerr << max_deg << endl;
  T result = dfs(0, -1);
  cout << result[0] << endl;
}