제출 #31618

#제출 시각아이디문제언어결과실행 시간메모리
31618ToMo01Beads and wires (APIO14_beads)C++14
28 / 100
1060 ms7552 KiB
/*input
5
1 2 10
1 3 40
1 4 15
1 5 20
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 200007;

int dp[N][2], par[N], n, ans;
vector<pair<int, int> > child[N];

void dfs(int u){
	for(auto v:child[u]){
		if(v.first == par[u]) continue;
		par[v.first] = u;
		dfs(v.first);
		dp[u][0] += max(dp[v.first][0], dp[v.first][1] + v.second);
	}

	for(auto v:child[u])
		if(v.first != par[u])
			dp[u][1] = max(dp[u][1], dp[u][0] + dp[v.first][0] + v.second - max(dp[v.first][0], dp[v.first][1] + v.second));
} 

int main(){
	cin >> n;
	for(int i = 1; i < n; ++i){
		int u, v, w; cin >> u >> v >> w;
		child[u].push_back({v, w});
		child[v].push_back({u, w});
	}	

	for(int i = 1; i <= n; ++i){
		memset(par, 0, sizeof par);
		memset(dp, 0, sizeof dp);

		for(int j = 1; j <= n; ++j)
			dp[j][1] = INT_MIN;

		dfs(i);
		ans = max(ans, dp[i][0]);
	}

	cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...