제출 #439664

#제출 시각아이디문제언어결과실행 시간메모리
439664soroush구슬과 끈 (APIO14_beads)C++17
57 / 100
8 ms1484 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int , int> pii; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 1e4 + 10; const ll mod = 1e9+7; #define pb push_back #define endl '\n' #define dokme(x) cout << x , exit(0) #define ms(x , y) memset(x , y , sizeof x) ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);} int n; int dp[maxn][2] , ans; vector < pii > adj[maxn]; void dfs(int v , int par = 0){ for(auto [u , w] : adj[v])if(u ^ par) dfs(u , v), dp[v][0] += max(dp[u][0] , dp[u][1] + w); dp[v][1] = -2e9 - 10; for(auto [u , w] : adj[v])if(u ^ par) dp[v][1] = max(dp[v][1] , dp[v][0] + w + dp[u][0] - max(dp[u][0] , dp[u][1] + w)); } void solve(int v , int par = 0){ ans = max(ans , dp[v][0]); int mx[2] = {int(-2e9 - 10) , int(-2e9 - 10)}; for(auto [u , w] : adj[v]){ mx[1] = max(mx[1] , dp[u][0] + w - max(dp[u][1] + w , dp[u][0])); if(mx[0] < mx[1])swap(mx[0] , mx[1]); } for(auto [u , w] : adj[v])if(u ^ par){ int a = dp[u][1] , b = dp[u][0] , c = dp[v][0] , d = dp[v][1]; bool imx = w + dp[u][0] - max(dp[u][0] , dp[u][1] + w) == mx[0]; dp[v][1] -= max(dp[u][0] , dp[u][1] + w); if(imx)dp[v][1] += mx[1] - mx[0]; dp[v][0] -= max(dp[u][0] , dp[u][1] + w); dp[u][1] += max(dp[v][0] , dp[v][1] + w); dp[u][1] = max(dp[u][1] , dp[u][0] + w + dp[v][0]); dp[u][0] += max(dp[v][0] , dp[v][1] + w); solve(u , v); dp[u][1] = a , dp[u][0] = b , dp[v][0] = c , dp[v][1] = d; } } int32_t main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin >> n; for(int i = 1 ; i < n ; i ++){ int a , b , c; cin >> a >> b >> c; adj[a].pb({b , c}); adj[b].pb({a , c}); } dfs(1); solve(1); cout << ans; 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...