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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
using ll=long long;
using namespace std;
const int C=200001, D=1751, E=2, H=(D-1)/2;
const ll Inf = 1000000000000000000ll;

int s[C], is=0, ip=1, pre[C], apre[C], par[C], ji[C];
ll value[C];
void proc_tree(int a, int n, vector <vector <int> > &tr, vector <vector <ll> > &ew){
	s[0]=a, is=1, pre[a]=1, apre[1]=a, ip=2;
	int b;
	
	for(int z=1; z<=n; z++) ji[z]=tr[z].size(), par[z]=0;
	
	while (is>0){
		a=s[is-1];
		if (ji[a]>0 && tr[a][ji[a]-1]==par[a]) ji[a]--;
		if (ji[a]>0){
		       	b=s[is]=tr[a][ji[a]-1];
			value[b] = ew[a][ji[a]-1];
			pre[b]=ip, apre[ip]=b;
		       	par[b]=a;
		       	ip++, is++, ji[a]--;
		}
		else is--;
	}
}

vector <vector <int> > tr(C);
vector <vector <ll> > ew(C);
bool exists[D][2], tmp_exists[D][2], valid_res[C][4];
ll dp[D][2], tmp_dp[D][2], res[C][4];
int main(){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	int a, b, n, i, ln, j, s1, s2;
	ll w;
	bool valid=false;

	scanf ("%d", &n);
	for (i=1; i<n; i++){
		scanf ("%d %d %lld", &a, &b, &w);
		tr[a].push_back(b), tr[b].push_back(a);
		ew[a].push_back(w), ew[b].push_back(w);
	}
	proc_tree(1, n, tr, ew);

	int parity, oddity;
	for (i=n; i>0; i--){
		a = apre[i];
		std::shuffle(tr[a].begin(), tr[a].end(), rng); //randomized children order
		ln = tr[a].size();

		s1 = MAX(0, H-ln-2);
		s2 = MIN(D, H+ln+2);
		for (oddity=s1; oddity<s2; oddity++){
		       for (parity=0; parity<2; parity++){
			       dp[oddity][parity] = -Inf;
			       exists[oddity][parity] = false;
		       }
		}
		dp[H][0] = 0, exists[H][0] = true;

		for (j=0; j<ln; j++){
			b = tr[a][j];
			if (par[a]==b) continue;

			s1 = MAX(0, H-j-2);
			s2 = MIN(D, H+j+2);
			for (oddity=s1; oddity<s2; oddity++){
			       for (parity=0; parity<2; parity++){
			       	       tmp_dp[oddity][parity] = dp[oddity][parity];
				       tmp_exists[oddity][parity] = exists[oddity][parity];
			       }
			}

			for (oddity=s1; oddity<s2; oddity++){
				for (parity=0; parity<2; parity++){
					valid = false;
					if (exists[oddity][parity] && valid_res[b][0]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][0]+dp[oddity][parity]), valid=true; //Move I: don't add any edge, profit off max
					if (exists[oddity][parity] && valid_res[b][3]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][3]+value[b]+dp[oddity][parity]), valid=true; //Move V: add an edge of length 3+1, no merging with anything other
					if (exists[oddity][1-parity] && valid_res[b][1]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][1]+value[b]+dp[oddity][1-parity]), valid=true; //Move III: Symmetric movement, add 1+1+two edges between
					if (oddity>0 && exists[oddity-1][parity] && valid_res[b][0]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][0]+value[b]+dp[oddity-1][parity]), valid=true; //Move II: one from this branch, three from second branch
					if (oddity<D-1 && exists[oddity+1][parity] && valid_res[b][2]) tmp_dp[oddity][parity] = MAX(tmp_dp[oddity][parity], res[b][2]+value[b]+dp[oddity+1][parity]), valid=true; //Move V: three from this branch, one from second branch
					tmp_exists[oddity][parity] = valid;
				}
			}

			for (oddity=s1; oddity<s2; oddity++){
			       for (parity=0; parity<2; parity++){
			       	       dp[oddity][parity] = tmp_dp[oddity][parity];
				       exists[oddity][parity] = tmp_exists[oddity][parity];
			       }
			}
		}

		if (exists[H][0]) res[a][0] = dp[H][0], valid_res[a][0]=true;
		if (exists[H+1][0]) res[a][1] = dp[H+1][0], valid_res[a][1]=true;
		if (exists[H][1]) res[a][2] = dp[H][1], valid_res[a][2]=true;
		if (exists[H-1][0]) res[a][3] = dp[H-1][0], valid_res[a][3]=true;
	}
	printf ("%lld\n", res[1][0]);
	
return 0;}