#line 1 "h.cpp" #include #line 1 "/home/ardririy/repos/cp-libs/libraries-cpp/input.hpp" #line 7 "/home/ardririy/repos/cp-libs/libraries-cpp/input.hpp" using namespace std; vector i64_vec_IN(int n) { vector res(n); for(int i=0; i> res[i]; } return res; } vector str_vec_IN(int n) { vector res(n); for(int i=0; i> res[i]; } return res; } vector> graph_IN(int n, int m) { vector> g(n); int u, v; for(int i=0; i> u >> v; u--; v--; g[u].emplace_back(v); g[v].emplace_back(u); } return g; } vector>> weighted_graph_IN(int n, int m) { vector>> g(n); int u, v; long long w; for(int i=0; i> u >> v >> w; u--; v--; g[u].push_back({v, w}); g[v].push_back({u, w}); } return g; } #line 3 "h.cpp" using namespace std; // using namespace atcoder; #define all(v) v.begin(),v.end() #define resort(v) sort(v.rbegin(),v.rend()) using ll = long long; using ull = unsigned long long; using vll=vector; using vvll = vector>; using P = pair; using vp=vector>; using djks=priority_queue>; const ll inf=1ll<<60; #define mod10 (ll)1e9+7 #define mod99 (ll)998244353 const double PI = acos(-1); #define rep(i,n) for (ll i=0;i=0;--i) #define rep2(i,a,n) for (ll i=a;i=a;--i) templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b>>& g, vector& dists, vector& seen) { seen[p] = true; ll res = 0; for(auto [ni, w]: g[p]) { if(seen[ni]) continue; ll ret = dfs1(ni, g, dists, seen); dists[p].push_back({ni, w+ret}); chmax(res, ret); } return res; } void dfs2(int p, vector& dists, ll n_w) { if(n_w!=-inf) { dists[p].push_back({1<<30, n_w}); } sort(all(dists[p]), [](const P& a, const P& b) { return a.second > b.second; }); if(dists[p][0].first!=1<<30) { int next_w=0; rep(i, min((int)dists[p].size(), 2)){ next_w += dists[p][i].second; } dfs2(dists[p][0].first, dists, next_w); } rep2(i, 1, dists[p].size()) { if(dists[p][i].first==1<<30) continue; dfs2(dists[p][i].first, dists, dists[p][0].second + dists[p][i].second); } } void solve() { int n; cin >> n; auto g = weighted_graph_IN(n, n-1); vector dists(n); vector seen(n, false); dfs1(0, g, dists, seen); dfs2(0, dists, -inf); ll ans = 0; rep(i,n) { ll s = 0; rep(j,min((int)dists[i].size(), 2)) { s += dists[i][j].second; } chmax(ans, s); } cout << ans << '\n'; } int main() { cin.tie(0); ios::sync_with_stdio(false); int t=1; //cin >> t; while(t--)solve(); }