제출 #731168

#제출 시각아이디문제언어결과실행 시간메모리
731168Cutebol구슬과 끈 (APIO14_beads)C++17
0 / 100
8 ms14412 KiB
#include <bits/stdc++.h> using namespace std; #define Nilou ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; #define int long long #define ff first #define ss second const int N = 2e5 + 5 ; const int mod = 1e9 + 7 ; const int inf = 1e15 ; int n , ans , x = inf ; set <int> d[N] ; vector <int> g[N] ; bool vis[N] ; map < int , map <int , int > > cost ; void dfs( int v ){ vis[v] = 1 ; for ( auto to : g[v] ) if ( !vis[to] ) dfs(to) ; } void solve(){ cin >> n ; for ( int i = 1 ; i < n ; i ++ ){ int x , y , c ; cin >> x >> y >> c ; g[x].push_back(y) ; g[y].push_back(x) ; cost[x][y] = c ; cost[y][x] = c ; ans += c ; } dfs (1) ; for ( int i = 1 ; i <= n ; i ++ ) if ( g[i].size() == 1 ) d[g[i][0]].insert(i) ; for ( int i = 1 ; i <= n ; i ++ ){ if ( !d[i].empty() ){ int a = inf , b = inf ; for ( auto j : d[i] ){ if ( a > b ) swap ( a , b ) ; b = min( b , cost[j][i] ) ; } if ( d[i].size()%2 ) x = min ( x , b ) ; else x = min ( x , a+b ) ; } } // cout << x << ' ' << ans << endl ; cout << ans - x << endl ; } signed main(){ Nilou ; int t = 1 ; // cin >> t ; while ( t -- ) solve() ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...