結果
問題 |
No.3113 The farthest point
|
ユーザー |
|
提出日時 | 2025-04-18 22:30:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 1,457 bytes |
コンパイル時間 | 2,105 ms |
コンパイル使用メモリ | 204,296 KB |
実行使用メモリ | 16,816 KB |
最終ジャッジ日時 | 2025-04-18 22:30:57 |
合計ジャッジ時間 | 4,881 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<pair<int,int>>> edges(n); i64 maxEdge = 0; // for the case all weights are negative for(int i = 0; i < n - 1; ++i){ int u, v, w; cin >> u >> v >> w; --u; --v; edges[u].emplace_back(v, w); edges[v].emplace_back(u, w); maxEdge = max(maxEdge, (i64)w); } vector<i64> dpDown(n, -1e18); i64 ans = maxEdge; // at least the single largest edge if all are negative // dfs(u, parent): computes dpDown[u] and updates ans auto dfs = [&](auto&& self, int u, int p) -> void { // collect best "downward" contributions from children vector<i64> bests; for(auto [v, w] : edges[u]){ if(v == p) continue; self(self, v, u); // either extend through v, or take just the edge u-v i64 contrib = max(dpDown[v] + w, (i64)w); bests.push_back(contrib); } if(bests.empty()){ dpDown[u] = 0; return; } std::sort(bests.begin(), bests.end(), greater<i64>()); i64 best1 = bests[0]; i64 best2 = bests[1]; ans = max(ans, best1); ans = max(ans, best1 + best2); dpDown[u] = best1; }; dfs(dfs, 0, -1); cout << ans << "\n"; return 0; }