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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <cstdio>
#include <cinttypes>
#include <vector>
#include <algorithm>
#define MAXN 300000
typedef long long ll;

// For each vertex, we want to calculate five numbers:
// What's the best value we can get out of this subtree (incl. edge to parent), if:
// - we don't take the edge to parent
// - we take the edge to parent, and continue it 0,1,2 or 3 edges into the subtree.
// Call these Val(0, v), Val(1, v), Val(2, v), Val(3, v), and Val(4, v).

// To calculate that, we'll basically choose, for each child vertex, what do we do
// with it and it's subtree. We've got 5 choices:
// -- not take the edge down
// -- take the edge down, but no further (and possibly some stuff in the subtree)
// -- take edge down and extend it by 2
// -- take edge down and extend it by 3
// -- take edge down and extend it to full 4 edges.
// Now, in the perfect world, we'd just calculate these five values for the children,
// choose the best for each child, and sum it up; voila, we've got the value for the
// parent. However, there are conditions: aside from the (potential) path which is the
// extension of the path coming from above, we need to have:
// -- an even number of length-2 extensions 
// -- an equal number of length-3 and length-1 extensions.
// So, we'll calculate a dynamic array D[a][k][n], where a is 0 or 1, K ranges from -N to N,
// and N ranges from 0 to number of children. The semantics are:
// D[a][k][n] is the best total value that can be had from the first n subtrees, constrained
// by the parity of length-2 extensions being a, and the difference between the number of
// length 3 and length 1 extensions being k (if positive, more length-3 extensions).
// The recursion is easy:
// D[0][0][0] = 0, D[a][k][0] = -infty for other a,k.
// D[a][k][n+1] = max of:
//   - D[a][k][n] + Val(0, v)
//   - D[a][k+1][n] + Val(1, v) 
//   - D[a^1][k][n] + Val(2, v)
//   - D[a][k-1][n] + Val(3, v)
//   - D[a][k][n] + Val(4, v)
// Where v is the n+1st child.
// And once we have D[*][*][num_children] calculated, we can calculate Val, if E is the
// cost of the edge to the parent. 
// Val(0, v) = D[0][0][num_c]
// Val(1, v) = D[0][0][num_c] + E
// Val(2, v) = D[0][-1][num_c] + E
// Val(3, v) = D[1][0][num_c] + E
// Val(4, v) = D[0][1][num_c] + E

// OK, cool. The only problem left is this is quadratic, and we don't have time for that.
// But there's a trick - we're calculating values D[*][k][*] for k far away from zero, but
// unlikely to use them. Say there's an optimal solution that takes K length-3 extensions
// (and so at most K+1 length-1 extensions). If we order the children randomly, it's very
// unlikely we'll actually need to go up all the way to K in the DP, since typically the
// order will be such that the ups and downs cancel out. Typically, you won't diverge more than
// sqrt(N) from the mean. So, we'll calculate D only with K up to ~sqrt(N) --- and, of course,
// we also calculate only up to the number of non-trivial length-3 extensions.
// (actually, we can optimize some more, let's see if we will). 

// One more observation is that we need the Val values for all vertices,
// but when doing the DP we only need the last column, so we'll do the standard mod 2 trick.

std::vector<int> children[MAXN];
std::vector<int> costs[MAXN];
int parent[MAXN];
ll parentcost[MAXN];
int stack[MAXN];
int stop;
ll val[5][MAXN];
ll D[2][2*MAXN][2]; // Parity of 2-ext, 3-ext minus 1-ext, parity of current child.

#define MINFTY -10000000000000000LL
#define SMINFTY -1000000000000000LL

int calc_maxK(int children) {
  // For now, let's try out the safe variant - we go up to children.
  if (children > 2500) return 2500;
  return std::max(children + 1, 1);
  // However, in reality we probably should cut this at somewhere like
  // sqrt(children) times some constant if children is large enough.
  // Note children is bounded by N / 3 (since these are depth-3 children),
  // so somewhere around 7 * 10^4, the square root of that is below 300.
  // Cutting to 1000 should be safe, but may be too slow?
  // Let's see how it runs.  
}

void calc_all(int v) {
  // Count the number of interesting size-3 children.
  int children_with_three = 0;
  for (int c : children[v]) {
    if (val[3][c] > SMINFTY) children_with_three++;
  }   
  const int maxK = calc_maxK(children_with_three);
  const int offset = maxK + 1;

  int prev = 0;
  int cur = 1;
  int cchild = 1;
  int numchildren = children[v].size();
  for (int a = 0; a < 2; ++a) for (int k = -maxK - 1; k <= maxK + 1; ++k) D[a][k + offset][prev] = MINFTY; 
  D[0][offset][prev] = 0;
  for (int c : children[v]) {
    ll v0 = std::max(val[0][c], val[4][c]);
    for (int a = 0; a < 2; ++a) {
      for (int k = offset - maxK; k <= offset + maxK; ++k) {
        D[a][k][cur] = std::max(
          std::max(D[a][k][prev] + v0, D[a][k+1][prev] + val[1][c]),
          std::max(D[1-a][k][prev] + val[2][c], D[a][k-1][prev] + val[3][c])); 
      }
      D[a][offset-maxK-1][cur] = D[a][offset+maxK+1][cur] = MINFTY;
    } 
    prev = 1 - prev;
    cur = 1 - cur;
    cchild += 1; 
  }  
  val[0][v] = D[0][offset][numchildren & 1];
  val[1][v] = D[0][offset][numchildren & 1] + parentcost[v];
  val[2][v] = D[0][offset-1][numchildren & 1] + parentcost[v];
  val[3][v] = D[1][offset][numchildren & 1] + parentcost[v];
  val[4][v] = D[0][offset+1][numchildren & 1] + parentcost[v];
}

int N;
int main() {
  scanf("%d", &N);
  if (N > 0) {
    for (int i = 0; i < N-1; ++i) {
      int A, B, C;
      scanf("%d %d %d", &A, &B, &C);
      children[A-1].push_back(B-1);
      children[B-1].push_back(A-1);    
      costs[A-1].push_back(C);
      costs[B-1].push_back(C);
    }
  } else {
    N = 200000;
    for (int i = 2; i <= N; i += 3) {
      children[0].push_back(i-1);
      children[i-1].push_back(0);
      costs[0].push_back(-i);
      costs[i-1].push_back(-i);
      children[i-1].push_back(i);
      children[i].push_back(i-1);
      costs[i].push_back(-i);
      costs[i-1].push_back(-i);
      children[i].push_back(i+1);
      children[i+1].push_back(i);
      costs[i].push_back(10 * i);
      costs[i+1].push_back(10 * i);
    }
  } 
  // Set the parent pointers, going through with a DFS. 
  stack[0] = 0;
  stop = 1;
  parent[0] = -1;
  while(stop) {
    int cv = stack[--stop];
    for (int child : children[cv]) {
      if (child != parent[cv]) {
        parent[child] = cv;
        stack[stop++] = child;
      }
    }
  }  
  // Remove parent from the children pointers.
  for (int v = 1; v < N; ++v) {
    int cvsize = children[v].size();
    for (int i = 0; i < cvsize; ++i) {
      if (children[v][i] == parent[v]) {
        parentcost[v] = costs[v][i];
        children[v][i] = children[v][cvsize - 1];
        // Note: costs array now mixed up, but we don't plan to use it.
      }
    } 
    children[v].pop_back();
    std::random_shuffle(children[v].begin(), children[v].end());
  }
  // Now, order the vertices in some traversal order where the parent is before children.
  stack[0] = 0;
  stop = 1;
  for (int i = 0; i < N; ++i) {
    int v = stack[i];
    int cvsize = children[v].size();
    for (int i = 0; i < cvsize; ++i) { 
      stack[stop++] = children[v][i];
    }
  } 
  // Now, stack is ordered so that parents go before children.
  for (int i = N-1; i >= 0; --i) {
    // Calculate children before parents.
    calc_all(stack[i]);
  }
  printf("%" PRId64 "\n", val[0][0]);
  return 0;    
}