제출 #372662

#제출 시각아이디문제언어결과실행 시간메모리
372662hivakarami구슬과 끈 (APIO14_beads)C++14
28 / 100
1071 ms5996 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define f first #define s second const int N = 2e5 + 100; const ll mod = 998244353; const ll inf = 1e9 + 100; ll dp[3][N], par[N]; vector<pair<int, int>> adj[N]; int n; void dfs(int u) { dp[1][u] = 0; for(auto it : adj[u]) { int x = it.f, w = it.s; if(x != par[u]) { par[x] = u; dfs(x); dp[1][u] += min(dp[1][x] + w, dp[2][x]); } } dp[2][u] = inf; for(auto it : adj[u]) { int x = it.f, w = it.s; if(x != par[u]) { ll mn = min(dp[1][x] + w, dp[2][x]); dp[2][u] = min(dp[2][u], dp[1][u] - mn + dp[1][x]); } } //cout << u << ' ' << dp[1][u] << ' ' << dp[2][u] << endl; } inline void cl() { for(int i = 0; i < n; i++) par[i] = i; } int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n; ll sum = 0; for(int i = 0; i < n-1; i++) { int x, y, w; cin >> x >> y >> w; x--; y--; adj[x].push_back({y, w}); adj[y].push_back({x, w}); sum += w; } ll mn = inf; for(int i = 0; i < n; i++) { cl(); dfs(i); mn = min(mn, dp[1][i]); } cout << sum - mn << endl; 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...