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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <cstdio>
#include <vector>

using namespace std;
typedef long long LL;

const int K = 4;
const LL INF = 1000000000000000000ll;

struct E {
  int p, c;
};

vector<vector<E>> es;

inline void mmax(LL& a, LL b) { if (b > a) a = b; }

struct S {
  LL s[4];
};

void subsolve(
    const vector<pair<S, int>>& sub,
    LL*& even_b,
    LL*& odd_b,
    LL*& even2_b,
    LL*& odd2_b,
    LL*& even,
    LL*& odd) {

  even_b = new LL[sub.size() * 2 + 3];
  odd_b = new LL[sub.size() * 2 + 3];
  even2_b = new LL[sub.size() * 2 + 3];
  odd2_b = new LL[sub.size() * 2 + 3];
  even = &even_b[sub.size() + 1];
  odd = &odd_b[sub.size() + 1];
  LL* even2 = &even2_b[sub.size() + 1];
  LL* odd2 = &odd2_b[sub.size() + 1];

  for (int i=-(int)sub.size() - 1; i<=(int)sub.size()+1; ++i) {
    even[i] = -INF * 2;
    odd[i] = -INF * 2;
    even2[i] = -INF * 2;
    odd2[i] = -INF * 2;
  }
  even[0] = 0;

  for (int i=0; i<sub.size(); ++i) {
    auto& [s, c] = sub[i];
    
    for (int j : {-i-1, i+1}) {
      odd2[j] = odd[j];
      even2[j] = even[j];
    }

    LL x = s.s[0] + c;
    LL y = s.s[1] + c;
    LL z = s.s[2] + c;
    LL t = max(max(s.s[3] + c, s.s[0]), 0ll);
    for (int j : {-i, i}) {
      odd2[j] = max(odd[j] + t, even[j] + y);
      even2[j] = max(even[j] + t, odd[j] + y);
    }
    for (int j=-i+1; j<=i-1; ++j) {
      odd2[j] = max(max(odd[j] + t, even[j] + y), max(odd[j+1] + z, odd[j-1] + x));
      even2[j] = max(max(even[j] + t, odd[j] + y), max(even[j+1] + z, even[j-1] + x));
    }
    for (int j=-i-1; j<=min(-i, i-1); ++j) {
      mmax(odd2[j], odd[j+1] + z);
      mmax(even2[j], even[j+1] + z);
    }  
    for (int j=max(i,-i+1); j<=i+1; ++j) {
      mmax(odd2[j], odd[j-1] + x);
      mmax(even2[j], even[j-1] + x);
    }

    swap(odd, odd2);
    swap(even, even2);
  }
}

S solve(int p, int q) {

  vector<pair<S, int>> sub[2];
  for (const E& e : es[p]) {
    if (e.p == q) continue;
    if (sub[0].size() <= sub[1].size()) {
      sub[0].push_back({solve(e.p, p), e.c});
    } else {
      sub[1].push_back({solve(e.p, p), e.c});
    }
  }

  LL* even_b[2];
  LL* odd_b[2];
  LL* even2_b[2];
  LL* odd2_b[2];
  LL* even[2];
  LL* odd[2];

  for (int i=0; i<2; ++i) {
    subsolve(sub[i], even_b[i], odd_b[i], even2_b[i], odd2_b[i], even[i], odd[i]);
  }

  S res;
  res.s[0] = even[0][0];
  res.s[1] = even[0][1];
  res.s[2] = odd[0][0];
  res.s[3] = even[0][-1];

  int size[2] = {sub[0].size(), sub[1].size()};
  for (int i=-size[1]; i<=size[1]; ++i) {
    mmax(res.s[0], even[0][-i] + even[1][i]);
    mmax(res.s[0], odd[0][-i] + odd[1][i]);

    mmax(res.s[1], even[0][-i+1] + even[1][i]);
    mmax(res.s[1], odd[0][-i+1] + odd[1][i]);
    
    mmax(res.s[2], even[0][-i] + odd[1][i]);
    mmax(res.s[2], odd[0][-i] + even[1][i]);
    
    mmax(res.s[3], even[0][-i-1] + even[1][i]);
    mmax(res.s[3], odd[0][-i-1] + odd[1][i]);
  }

//  printf("Recurse %d -> %d\n", q+1, p+1);
//  printf("Sub size %d\n", sub.size());
//  printf("Solution: %lld %lld %lld %lld\n\n", res.s[0], res.s[1], res.s[2], res.s[3]); 

  for (int i=0; i<2; ++i) {
    delete[] even_b[i];
    delete[] odd_b[i];
    delete[] even2_b[i];
    delete[] odd2_b[i];
  }

  return res;
}

int main() {
  int n; scanf("%d", &n);
  es.resize(n);

  for (int i=0; i<n-1; ++i) {
    int a, b, c; scanf("%d %d %d", &a, &b, &c); --a; --b;
    es[a].push_back({b, c});
    es[b].push_back({a, c});
  }
  
  S s = solve(0, -1);
  printf("%lld\n", s.s[0]);
}