제출 #106076

#제출 시각아이디문제언어결과실행 시간메모리
106076Saboon구슬과 끈 (APIO14_beads)C++14
28 / 100
137 ms5248 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 2e5 + 10;
const int inf = 1e8;
 
int dp[maxn], pd[maxn];
vector<pair<int, int> > t[maxn];
 
void dfs(int v, int par = -1){
	int mx = -inf;
	dp[v] = 0;
	for (auto edge : t[v]){
		int u = edge.first, c = edge.second;
		if (u != par){
			dfs(u, v);
			dp[v] += max(dp[u], pd[u] + c);
			mx = max(mx, dp[u] + c - max(dp[u], pd[u] + c)); 
		}
	}
	pd[v] = dp[v] + mx;
}
 
int main(){
	ios_base::sync_with_stdio (false);
	int n;
	cin >> n;
	for (int i = 1; i <= n - 1; i++){
		int v, u, c;
		cin >> v >> u >> c;
		t[v].push_back({u, c});
		t[u].push_back({v, c});
	}
	int answer = 0;
	for (int i = 1; i <= 1000; i++){
		int v = rand() % n + 1;
		dfs(v);
		answer = max(answer, dp[v]);
	}
	cout << answer << 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...