#include using namespace std; #include using namespace atcoder; const long long INF = 1e18; using ll = long long; struct VertexAddSubtreeSum { int n; vector> edge; vector et, et1, et2, de, l, et1s; VertexAddSubtreeSum(int n, vector> edge): n(n), edge(edge) { vector P(n, -1), Q; Q.push_back(-0-1); Q.push_back(0); int ct = -1, depth = -1; et1.assign(n, 0); et2.assign(n, 0); de.assign(n, 0); while (!Q.empty()) { int i = Q.back(); Q.pop_back(); if (i < 0) { ct++; et.push_back(i); et2[-i-1] = ct; depth--; continue; } et.push_back(i); ct++; if (et1[i] == 0) et1[i] = ct; depth++; de[i] = depth; for (int j = edge[i].size() - 1; j >= 0; j--) { int a = edge[i][j]; if (a != P[i]) { P[a] = i; edge[a].erase(remove(edge[a].begin(), edge[a].end(), i), edge[a].end()); Q.push_back(-a-1); Q.push_back(a); } } } l.resize(n); iota(l.begin(), l.end(), 0); sort(l.begin(), l.end(), [&](int x, int y) { return et1[x] < et1[y]; }); et1s = et1; sort(et1s.begin(),et1s.end()); } pair subtree(int x) { int left = et1[x], right = et2[x]; int lft = lower_bound(et1s.begin(), et1s.end(), left) - et1s.begin(); int rgt = lower_bound(et1s.begin(), et1s.end(), right) - et1s.begin(); return {lft, rgt}; } }; ll op(ll x,ll y){return max(x,y);} ll e(){return -1LL<<60;} ll op2(ll x,ll y){return x+y;} ll id(){return 0;} int main() { int n; cin >> n; vector> edge(n); unordered_map cc; for (int i = 0; i < n - 1; ++i) { int u, v; long long w; cin >> u >> v >> w; u--; v--; edge[u].push_back(v); edge[v].push_back(u); cc[1LL * u * n + v] = w; cc[1LL * v * n + u] = w; } // BFS vector dist(n, INF), dist2(n, 0); vector p(n, -1); deque dq; dq.push_back(0); dist[0] = 0; while (!dq.empty()) { int now = dq.front(); dq.pop_front(); for (int to : edge[now]) { if (dist[to] > dist[now] + 1) { dist[to] = dist[now] + 1; dist2[to] = dist2[now] + cc[1LL * to * n + now]; dq.push_back(to); p[to] = now; } } } VertexAddSubtreeSum v1(n, edge); lazy_segtree lst1(n); for (int i = 0; i < n; ++i) { lst1.set(i, dist2[v1.l[i]]); } vector a(n, -1); auto [l0, r0] = v1.subtree(0); for (int i : v1.et) { if (i >= 0) { if (i != 0) { long long cost = cc[1LL * p[i] * n + i]; auto [l, r] = v1.subtree(i); lst1.apply(l, r, -2 * cost); lst1.apply(l0, r0, cost); } a[i] = lst1.all_prod(); } else { int j = ~i; long long cost = cc[1LL * p[j] * n + j]; auto [l, r] = v1.subtree(j); lst1.apply(l, r, 2 * cost); lst1.apply(l0, r0, -cost); } } cout << *max_element(a.begin(), a.end()) << endl; return 0; }