#ifndef MAIN #define MAIN #include __FILE__ int op(int a, int b) { return max(a, b); } int e() { return 0; } void _main(){ cint(n); vector> v(n, vector(0)); rep(i, n-1) { cint(a, b, c); --a; --b; v[a] += {b, c}; v[b] += {a, c}; } vector dic(n, -1), p(n, -1), dic2(n, -1); vector> dpc(n, vector(0)); vector> dps(n); rep(i, n) { dpc[i] = vector(v[i].size(), -1); dps[i] = Segtree(v[i].size()); } vector s(n, 0); auto dfs = [&](auto dfs, int arg) -> int { s[arg] = 1; int ret = 0; int i = -1; for (auto [k, u] : v[arg]) { i++; if (s[k]) { dic2[arg] = i; continue; } p[k] = arg; dic[k] = i; ret = max(ret, dpc[arg][i] = dfs(dfs, k) + u); dps[arg].set(i, dpc[arg][i]); } return ret; }; dfs(dfs, 0); fill(all(s), 0); auto dfs2 = [&](auto dfs2, int arg) -> void { s[arg] = 1; if (p[arg] != -1) { dps[arg].set(dic2[arg], dpc[arg][dic2[arg]] = max(dps[p[arg]].prod(0, dic[arg]), dps[p[arg]].prod(dic[arg]+1, dpc[p[arg]].size())) + v[p[arg]][dic[arg]][1]); } for (auto [k, u] : v[arg]) { if (s[k]) continue; dfs2(dfs2, k); } }; dfs2(dfs2, 0); int ans = 0; for (auto& seg : dps) ans = max(ans, seg.all_prod()); cout << ans << endl; } #else #define MAIN #include using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using strvec = vector; constexpr ll mod10 = 1000000007; constexpr ll mod9 = 998244353; constexpr ll inf = 10000000000000000; #define int ll #define double ld #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repf(i, s, n) for (int i = s; i < (int)(n); i++) template void __y_input(Args &...arg) { (cin >> ... >> arg); } template void __y_input_vec_1(int p, Args &...args) { (cin >> ... >> args[p]); } template void __y_input_vec_resize(int size, Arg &arg) { arg.resize(size); } template void __y_input_vec(int n, Args &...args) { (__y_input_vec_resize(n, args), ...); rep(i, n) { (__y_input_vec_1(i, args), ...); } } #define cint(...) \ int __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cdbl(...) \ double __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cstr(...) \ string __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cvec(n, ...) \ vector __VA_ARGS__; \ __y_input_vec(n, __VA_ARGS__) #define cvect(t, n, ...) \ vector __VA_ARGS__; \ __y_input_vec(n, __VA_ARGS__) #define last cout << endl #define yn(bl) (bl ? "Yes" : "No") #define all(v) v.begin(), v.end() #define acc(v) accumulate(v.begin(), v.end(), 0LL) #define nxp(v) next_permutation(v.begin(), v.end()) ostream &yesno(bool bl) { cout << yn(bl); return cout; } void cyn(bool bl){ cout << (bl ? "Yes" : "No") << endl; } typedef array xy; typedef array xyz; template inline void sort(T &vec) { return sort(vec.begin(), vec.end()); } template inline void rsort(T &vec) { return sort(vec.rbegin(), vec.rend()); } void _main(); template void prefix_sum(vector& p, vector& s){ s.emplace_back(p[0]); for (size_t i = 1; i < p.size(); i++){ s.emplace_back(p[i] + s.back()); } return; } template void compress(T a, T b){ vector m(a, b); sort(all(m)); m.erase(unique(all(m)), m.end()); for (auto itr = a; itr != b; itr++){ *itr = (lower_bound(all(m), *itr) - m.begin()); } } template using rpq = priority_queue, greater>; template void operator+=(vector& v, const T t) { v.emplace_back(t); } template struct Segtree { std::vector Tree; int n; int depth = 1, width = 1; Segtree(int N = 0) : n(N) { while (width < n) depth++, width <<= 1; Tree.resize(width * 2); for (int i = width; i < width * 2; i++) Tree[i] = e(); for (int i = width-1; i >= 0; i--) Tree[i] = op(Tree[i<<1], Tree[i<<1|1]); } Segtree(std::vector v) { n = v.size(); while (width < n) depth++, width <<= 1; Tree.resize(width * 2); for (int i = width; i < width * 2; i++) Tree[i] = (i < width + n ? v[i - width] : e()); for (int i = width-1; i >= 0; i--) Tree[i] = op(Tree[i<<1], Tree[i<<1|1]); } void set(int pos, S val) { pos += width; Tree[pos] = val; for (int c = (pos >> 1); c > 0; c >>= 1) Tree[c] = op(Tree[c<<1], Tree[c<<1|1]); return; } S get(int pos) { return Tree[width + pos]; } S all_prod() { return Tree[1]; } S prod(int l, int r) { S x = e(), y = e(); l += width, r += width; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) x = op(x, Tree[l++]); if (r & 1) y = op(Tree[--r], y); } return op(x, y); } }; signed main() { cin.tie(0); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); _main(); return 0; } #endif