제출 #916287

#제출 시각아이디문제언어결과실행 시간메모리
916287Alcabel구슬과 끈 (APIO14_beads)C++17
28 / 100
1043 ms6492 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5; const long long inf = 1e11; vector<pair<int, int>> g[maxn]; long long dp[maxn][2]; void dfsCalc(int v, int p) { dp[v][0] = 0, dp[v][1] = -inf; for (const auto& [u, w] : g[v]) { if (u != p) { dfsCalc(u, v); dp[v][0] += max(dp[u][0], dp[u][1] + w); } } for (const auto& [u, w] : g[v]) { if (u != p) { dp[v][1] = max(dp[v][1], dp[v][0] - max(dp[u][0], dp[u][1] + w) + dp[u][0] + w); } } } void solve() { int n; cin >> n; for (int i = 0; i < n - 1; ++i) { int v, u, w; cin >> v >> u >> w; --v, --u; g[v].emplace_back(u, w); g[u].emplace_back(v, w); } long long ans = 0; for (int r = 0; r < n; ++r) { dfsCalc(r, -1); ans = max(ans, dp[r][0]); } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int T = 1; cin >> T; while (T--) { solve(); cerr << "-----------\n"; cout << "-----------\n"; } #else int T = 1; // cin >> T; while (T--) { solve(); } #endif 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...