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
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = b; a <= i; i--)
#define cat(x) cerr << #x << " = " << x << '\n';
using ll = long long;
using namespace std;

const int N = 200200;
const ll inf = 1e18;
const int M = 475;

inline void upd(ll &a, const ll b) {
	a = max(a, b);
}

int n;
vector<pair<int, int>> e[N];
ll f[N][4];
vector<ll> dp[N][2], g[2];

void dfs(int u, int p) {
	int sz = max(1, min(M, int(e[u].size()) / 2));
	dp[u][0].resize(2 * sz + 1, -inf);
	dp[u][1].resize(2 * sz + 1, -inf);
	dp[u][0][sz] = 0;

	int cnt = 0;
	for (auto [v, w] : e[u]) {
		if (v == p)
			continue;

		dfs(v, u);

		g[0].resize(2 * sz + 1);
		fill(g[0].begin(), g[0].end(), -inf);
		g[1].resize(2 * sz + 1);
		fill(g[1].begin(), g[1].end(), -inf);

		int L = max(0, sz - cnt);
		int R = min(2 * sz, sz + cnt);

		ll cur;
		rep(j, 0, 1) {
			rep(i, L, R) {
				cur = dp[u][j][i];
				if (cur == -inf)
					continue;
				// 0 without edge
				upd(g[j][i], cur + f[v][0]);
				cur += w;
				// 0 with edge
				if (i + 1 <= 2 * sz)
					upd(g[j][i + 1], cur + f[v][0]);
				// 1
				upd(g[j ^ 1][i], cur + f[v][1]);
				// 2
				if (0 <= i - 1)
					upd(g[j][i - 1], cur + f[v][2]);
				// 3
				upd(g[j][i], cur + f[v][3]);
			}
		}

		dp[u][0] = g[0];
		dp[u][1] = g[1];
		cnt++;
	}

	f[u][0] = dp[u][0][sz];
	f[u][1] = dp[u][0][sz + 1];
	f[u][2] = dp[u][1][sz];
	f[u][3] = dp[u][0][sz - 1];
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	srand(233);

	cin >> n;
	rep(i, 2, n) {
		int a, b, c;
		cin >> a >> b >> c;
		e[a].push_back({b, c});
		e[b].push_back({a, c});
	}

	rep(i, 1, n) {
		random_shuffle(e[i].begin(), e[i].end());
	}

	dfs(1, 0);

	cout << f[1][0] << '\n';
	return 0;
}