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
#include <vector>
#include <iostream>
#include <array>
#include <cinttypes>
#include <cstring>
#include <climits>
#include <string>
using namespace std;
struct edge
{
	int a, b, v;
};
namespace brut
{
	struct E
	{
		int dest;
		int value;
	};
	template<class T> void maximize(T & a, T b) {if(a < b) a = b;}
	vector<array<int64_t, 4>> dp;
	vector<bool> odw;
	vector<vector<E>> g;

	array<array<array<int64_t, 400100>, 2>, 2> xd;

	void dfs(int p)
	{
		odw[p] = 1;
		for(auto [dest, value] : g[p])
		{
			if(odw[dest]) continue;
			dfs(dest);
			odw[dest] = 0;
		}
		
		int xd_counter = 0;
		xd[0][0][0] = 0;
		xd[0][1][0] = -1e18;
		auto find_dp = [&]() -> array<int64_t, 4>
		{
			for(auto [dest, value] : g[p])
			{
				if(odw[dest]) continue;
				int new_counter = xd_counter + 1;
				for(int i = 0; i <= 2 * new_counter; ++i)
				{
					xd[new_counter % 2][0][i] = xd[new_counter % 2][1][i] = -1e18;
				}
				for(int i = 0; i <= 2 * xd_counter; ++i)
				{
					for(int k = 0; k < 2; ++k)
					{
					//Do nothing
						maximize(xd[new_counter % 2][k][i + 1], xd[xd_counter % 2][k][i] + dp[dest][0]);
					//Finish
						maximize(xd[new_counter % 2][k][i + 1], xd[xd_counter % 2][k][i] + dp[dest][3] + value);
					//Add dp[1] (flip)
						maximize(xd[new_counter % 2][k][i + 1], xd[xd_counter % 2][k ^ 1][i] + dp[dest][1] + value);
					//Add dp[0] (+1)
						maximize(xd[new_counter % 2][k][i + 1 + 1], xd[xd_counter % 2][k][i] + dp[dest][0] + value);
					//Add dp[2] (-1)
						maximize(xd[new_counter % 2][k][i + 1 - 1], xd[xd_counter % 2][k][i] + dp[dest][2] + value);
					}
				}
				xd_counter = new_counter;
			}
			if(xd_counter == 0) return {0, (int64_t)-1e18, (int64_t)-1e18, (int64_t)-1e18};
			else return {xd[xd_counter % 2][0][xd_counter], xd[xd_counter % 2][0][xd_counter + 1], xd[xd_counter % 2][1][xd_counter], xd[xd_counter % 2][0][xd_counter - 1]};
		};

		dp[p] = find_dp();
	}
}
int64_t solve_brut(int n, const vector<edge>& edges)
{
	using namespace brut;
	g = vector<vector<E>>(n + 1);
	dp = vector<array<int64_t, 4>>(n + 1, {0, 0, 0, 0});
	odw = vector<bool>(n + 1, false);
	for(auto [a, b, v] : edges)
	{
		g[a].push_back({b, v});
		g[b].push_back({a, v});
	}
	dfs(1);
	return dp[1][0];
}
#define solve_wzor solve_brut
#include <iostream>
#include <vector>

int main()
{
	int n;
	std::cin >> n;
	std::vector<edge> edges(n - 1);
	for(int i = 0; i < n - 1; ++i)
	{
		std::cin >> edges[i].a >> edges[i].b >> edges[i].v;
	}
	std::cout << solve_wzor(n, edges) << '\n';
}