제출 #1339343

#제출 시각아이디문제언어결과실행 시간메모리
1339343javkhlantogs구슬과 끈 (APIO14_beads)C++20
28 / 100
1096 ms12076 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<pair<ll,ll>>> e;
vector<vector<ll>> dp(200001,vector<ll>(2));
void dfs(ll u,ll p){
	ll val=-1e18,gain;
	dp[u][0]=dp[u][1]=0;
	for(auto v:e[u]){
		if(v.first==p) continue;
		dfs(v.first,u);
		dp[u][0]+=max(dp[v.first][1]+v.second,dp[v.first][0]);
		dp[u][1]+=max(dp[v.first][1]+v.second,dp[v.first][0]);
		gain=dp[v.first][0]+v.second-max(dp[v.first][1]+v.second,dp[v.first][0]);
		if(gain>=val) val=gain;
	}
	if(e[u].size()!=1) dp[u][1]=dp[u][1]+val;
		else dp[u][1]=-1e18;
}
int main(){
	ll n,i,j,k,q;
	cin>>n;
	e.resize(n+1);
	for(i=0 ; i<n-1 ; i++){
		cin>>j>>k>>q;
		e[j].push_back({k,q});
		e[k].push_back({j,q});
	}
	ll ans=0;
	for(i=1 ; i<=n ; i++){
		dfs(i,i);
		ans=max(ans,dp[i][0]);
	}
	cout<<ans<<"\n";
	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...