제출 #265490

#제출 시각아이디문제언어결과실행 시간메모리
265490square1001Beads and wires (APIO14_beads)C++14
28 / 100
1089 ms1280 KiB
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const long long inf = 1LL << 40;
class edge {
public:
	int to; long long cost;
	edge() : to(-1), cost(0LL) {};
	edge(int to_, long long cost_) : to(to_), cost(cost_) {};
};
int main() {
	// step #1. read input
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<vector<edge> > G(N);
	for(int i = 0; i < N - 1; ++i) {
		int a, b; long long w;
		cin >> a >> b >> w; --a, --b;
		G[a].push_back(edge(b, w));
		G[b].push_back(edge(a, w));
	}
	// step #2. calculation
	function<pair<long long, long long>(int, int)> solve = [&](int pos, int pre) {
		// returns = (no mid-blue, one mid-blue)
		long long sumcost = 0, delta = -inf;
		for(edge e : G[pos]) {
			if(e.to == pre) continue;
			pair<long long, long long> res = solve(e.to, pos);
			sumcost += max(res.first, res.second + e.cost);
			delta = max(delta, e.cost - max(res.second + e.cost - res.first, 0LL));
		}
		return make_pair(sumcost, sumcost + delta);
	};
	long long ans = 0;
	for(int i = 0; i < N; ++i) {
		pair<long long, long long> res = solve(i, -1);
		ans = max(ans, res.first);
	}
	cout << ans << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...