제출 #722566

#제출 시각아이디문제언어결과실행 시간메모리
722566stevancv구슬과 끈 (APIO14_beads)C++14
0 / 100
3 ms5028 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 2e5 + 2; const int inf = 1e9; vector<pair<int, int>> g[N]; int dp[N][2]; void Dfs(int s, int e, int val) { vector<int> all; int sum = 0; for (auto z : g[s]) { int u = z.first; int v = z.second; if (u == e) continue; Dfs(u, s, v); sum += max(dp[u][0], dp[u][1]); all.push_back(v + dp[u][0] - max(dp[u][0], dp[u][1])); } sort(all.rbegin(), all.rend()); dp[s][0] = sum; if (all.size() > 0) dp[s][1] = sum + all[0] + val; if (all.size() > 1) smax(dp[s][0], sum + all[0] + all[1]); if (all.size() == 0) dp[s][1] = -inf; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i < n - 1; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); } Dfs(1, 0, 0); cout << dp[1][0] << en; 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...