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
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
mt19937 rng(195101);

const int nax = 200 * 1000 + 10;
const ll INF = 1e18;
int n, C;
vector<pi>V[nax];
ll dp[nax][4], val[4];
ll DP[2][2][nax];

void dfs(int x, int p) {
	for(auto nbh : V[x]) if(nbh.ST != p) {
		dfs(nbh.ST, x);
	}
	int memoC = C;
	C = min(C, (int)V[x].size());
	C = max(C, 5);
	for(int i = 0; i <= 2 * C; ++i) {
		DP[0][0][i] = DP[0][1][i] = -INF;
	}
	DP[0][0][C] = 0;
	int bt = 1;
	for(auto nbh : V[x]) if(nbh.ST != p) {
		for(int i = 0; i < 4; ++i) {
			val[(i + 1) % 4] = dp[nbh.ST][i] + nbh.ND;
		}
		val[0] = max(val[0], dp[nbh.ST][0]);
		for(int i = 0; i <= 2*C; ++i) {
			for(int bit = 0; bit < 2; ++bit) {
				DP[bt][bit][i] = max(DP[bt^1][bit][i] + val[0], DP[bt^1][bit^1][i] + val[2]);
				if(i + 1 <= 2 * C) {
					DP[bt][bit][i] = max(DP[bt][bit][i], DP[bt^1][bit][i + 1] + val[1]);
				if(i - 1 >= 0)
					DP[bt][bit][i] = max(DP[bt][bit][i], DP[bt^1][bit][i - 1] + val[3]);
				}
			}
		}
		bt ^= 1;
	}
	bt ^= 1;
	dp[x][0] = DP[bt][0][C];
	dp[x][1] = DP[bt][0][C - 1];
	dp[x][2] = DP[bt][1][C];
	dp[x][3] = DP[bt][0][C + 1];
	C = memoC;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int u,v,c,i = 1; i < n; ++i) {
		cin >> u >> v >> c;
		V[u].emplace_back(v, c);
		V[v].emplace_back(u, c);
	}
	for(int i = 1; i <= n; ++i) {
		shuffle(V[i].begin(), V[i].end(), rng);
	}
	C = n/2+1;
	C = max(C, 10);
	C = min(C, 1000);
	int root = (rng() % n) + 1;
	dfs(root, 0);
	cout << dp[root][0];
}