이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
#define int long long
using namespace std ;
const int MAXN = 1001 * 1001 ;
vector<pair<int,int>> adj[MAXN] ;
int dp[MAXN] , pd[MAXN] ;
void dfs(int u , int p)
{
dp[u] = 0 ;
pd[u] = -1e17 ;
vector<pair<int,int>> child ;
for(auto v : adj[u])
{
if(v.F==p) continue ;
dfs(v.F,u) ;
child.pb(v) ;
}
if(!child.size()) return ;
if(child.size()==1)
{
int v = child[0].F , w = child[0].S ;
pd[u] = w + dp[v] ;
dp[u] = max(dp[v],w+pd[v]) ;
return ;
}
int sum = 0 ;
for(auto v : child) sum += max(dp[v.F],v.S+pd[v.F]) ;
for(auto v : child) pd[u] = max(pd[u],sum-max(dp[v.F],v.S+pd[v.F])+v.S+dp[v.F]) ;
dp[u] = sum ;
vector<int> val ;
for(auto v : child)
{
val.pb(v.S+dp[v.F]-max(dp[v.F],v.S+pd[v.F])) ;
}
sort(val.rbegin(),val.rend()) ;
dp[u] = max(dp[u],sum+val[0]+val[1]) ;
}
int32_t main()
{
ios::sync_with_stdio(0) ; cin.tie(0) ;
int n ;
cin >> n ;
for(int i = 1 ; i < n ; i ++ )
{
int x , y , z ;
cin >> x >> y >> z ;
adj[x].pb({y,z}) ;
adj[y].pb({x,z}) ;
}
int ans = 1e18 ;
for(int i = 1 ; i <= n ; i ++ ) {
dfs(i,0) ;
ans = min(ans,dp[i]) ;
}
cout << ans << endl ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |