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
#include<bits/stdc++.h>
using namespace std;
using lld = long long;

const int MAXN = 2e5;
const lld INF = 1e18;

struct DP {
	lld zero = 0;
	lld one = -INF;
	lld two = -INF;
	lld three = -INF;
};

struct Node {
	vector<pair<int,lld>> path;
	bool vis = false;
	DP value;
};

lld X[2][2*MAXN+1], Y[2][2*MAXN+1];

void solve(vector<Node>& g, int v) {
	g[v].vis = true;
	int n = 0;
	for(auto [u,w] : g[v].path)
		if(!g[u].vis) solve(g,u), n++;
	g[v].vis = false;

	if(n == 0) return;

	fill(X[0], X[0]+2*n+1, -INF);
	fill(Y[0], Y[0]+2*n+1, -INF);
	X[0][n] = 0;

	int l = 1,r = 0;
	for(auto [u, w] : g[v].path)
		if(!g[u].vis) {
			l = 1-l, r = 1-r;

			// CLEAR
			fill(X[r], X[r]+2*n+1, -INF);
			fill(Y[r], Y[r]+2*n+1, -INF);
			X[r][n] = 0;

			// ZERO
			for(int i=0;i<=2*n;i++) {
				X[r][i] = max(X[r][i], X[l][i] + max(g[u].value.zero, g[u].value.three + w));
				Y[r][i] = max(Y[r][i], Y[l][i] + max(g[u].value.zero, g[u].value.three + w));
			}

			// ONE
			for(int i=1;i<=2*n;i++) {
				X[r][i] = max(X[r][i], X[l][i-1] + g[u].value.zero + w);
				Y[r][i] = max(Y[r][i], Y[l][i-1] + g[u].value.zero + w);
			}

			// TWO
			for(int i=0;i<=2*n;i++) {
				X[r][i] = max(X[r][i], Y[l][i] + g[u].value.one + w);
				Y[r][i] = max(Y[r][i], X[l][i] + g[u].value.one + w);
			}

			// THREE
			for(int i=0;i<=2*n-1;i++) {
				X[r][i] = max(X[r][i], X[l][i+1] + g[u].value.two + w);
				Y[r][i] = max(Y[r][i], Y[l][i+1] + g[u].value.two + w);
			}
		}

	g[v].value.zero = X[r][n];
	g[v].value.one = X[r][n+1];
	g[v].value.two = Y[r][n];
	g[v].value.three = X[r][n-1];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<Node> g(n);
	for(int i=0;i<n-1;i++) {
		int a,b,c;
		cin >> a >> b >> c, a--, b--;
		g[a].path.push_back({b,c});
		g[b].path.push_back({a,c});
	}

	solve(g,0);
	cout << g[0].value.zero << "\n";

	return 0;
}