#include using namespace std; #define rep(i, x, limit) for (long long i = (long long)x; i < (long long)limit; i++) #define REP(i, x, limit) for (long long i = (long long)x; i <= (long long)limit; i++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define el '\n' #define spa " " #define Yes cout << "Yes" << el #define No cout << "No" << el #define YES cout << "YES" << el #define NO cout << "NO" << el #define eps (1e-10) #define Equals(a,b) (fabs((a) - (b)) < eps ) #define debug(x) cerr << #x << " = " << x << el using ll = long long; using ull = unsigned long long; using pii = pair; using pll = pair; using vi = vector; using vl = vector; using vvl = vector>; using vs = vector; using vb = vector; const double pi = 3.141592653589793238; const int inf = 1073741823; const ll infl = 1LL << 60; const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string abc = "abcdefghijklmnopqrstuvwxyz"; const ll MOD = 998244353; #include using namespace atcoder; using mint = modint998244353; using vm = vector; // Requires: #include (or ) // Also needs: , using namespace std; struct Edge { long long to, cost; }; struct S_rmq { long long value; long long index; }; S_rmq op_rmq(S_rmq a, S_rmq b){ if(a.value < b.value) return a; else return b; } S_rmq E_rmq(){ return {(1LL << 60), -1LL}; } struct S_rsq { long long value; }; S_rsq op_rsq(S_rsq a, S_rsq b){ return {a.value + b.value}; } S_rsq E_rsq(){ return {0}; } struct weighted_euler_tour { std::vector depth, visit, cost1, cost2; std::vector discover, finishing; std::vector> g; long long n; std::map, long long> edge_index1; std::map, long long> edge_index2; atcoder::segtree rmq; atcoder::segtree rsq1; atcoder::segtree rsq2; weighted_euler_tour(long long n=1, std::vector> g=std::vector>()){ init(n, g); } void init(long long n, std::vector> g){ this->n = n; depth.clear(); visit.clear(); cost1.clear(); cost2.clear(); discover.assign(n, (1LL<<30)); finishing.assign(n, -1); edge_index1.clear(); edge_index2.clear(); this->g = std::move(g); this->g.resize(n); } void add_edge(long long u, long long v, long long cost){ g[u].push_back({v, cost}); g[v].push_back({u, cost}); } void dfs(long long root){ // If you might call dfs() multiple times, clear these: // depth.clear(); visit.clear(); cost1.clear(); cost2.clear(); cost1.push_back(0); cost2.push_back(0); Dfs(root, -1, 0); for(long long i=0;i<(long long)visit.size();i++){ discover[visit[i]] = std::min(discover[visit[i]], i); finishing[visit[i]] = std::max(finishing[visit[i]], i+1); } std::vector depth_v((int)depth.size()); for(long long i=0; i<(long long)depth.size(); i++){ depth_v[i] = {depth[i], visit[i]}; } std::vector cost1_v((int)cost1.size()); for(long long i=0; i<(long long)cost1.size(); i++){ cost1_v[i] = {cost1[i]}; } std::vector cost2_v((int)cost2.size()); for(long long i=0; i<(long long)cost2.size(); i++){ cost2_v[i] = {cost2[i]}; } rmq = atcoder::segtree(depth_v); rsq1 = atcoder::segtree(cost1_v); rsq2 = atcoder::segtree(cost2_v); } void Dfs(long long v, long long p, long long d) { visit.push_back(v); depth.push_back(d); for (Edge u : g[v]) { if (u.to == p) continue; cost1.push_back(u.cost); cost2.push_back(u.cost); edge_index1[{std::min(v,u.to), std::max(v,u.to)}] = (long long)cost1.size()-1; edge_index2[{v, u.to}] = (long long)cost2.size()-1; Dfs(u.to, v, d + 1); visit.push_back(v); depth.push_back(d); cost1.push_back(0); cost2.push_back(-u.cost); edge_index2[{u.to, v}] = (long long)cost2.size()-1; } } long long lca(long long u, long long v){ // FIX: segtree::prod is [l, r), so right end must be +1 long long l = std::min(discover[u], discover[v]); long long r = std::max(discover[u], discover[v]) + 1; return rmq.prod(l, r).index; } long long pe(long long u){ return rsq2.prod(0, discover[u]+1).value; } long long dist(long long u, long long v){ if(u==v) return 0; return pe(u) + pe(v) - 2*pe(lca(u,v)); } long long sum(long long x){ return rsq1.prod(discover[x], finishing[x]).value; } void update(long long u, long long v, long long x){ if(u > v) std::swap(u,v); if(edge_index1.find({u,v})==edge_index1.end()) return; rsq1.set(edge_index1[{u,v}], {x}); // make u the shallower endpoint (parent) in the rooted tree if(depth[discover[u]] > depth[discover[v]]) std::swap(u,v); rsq2.set(edge_index2[{u,v}], {x}); rsq2.set(edge_index2[{v,u}], {-x}); } void add(long long u, long long v, long long x){ if(u > v) std::swap(u,v); if(edge_index1.find({u,v})==edge_index1.end()) return; long long idx1 = edge_index1[{u,v}]; rsq1.set(idx1, {rsq1.prod(idx1, idx1+1).value + x}); // FIX: depth[] is indexed by Euler position; use depth[discover[*]] if(depth[discover[u]] > depth[discover[v]]) std::swap(u,v); long long idx_uv = edge_index2[{u,v}]; long long idx_vu = edge_index2[{v,u}]; rsq2.set(idx_uv, {rsq2.prod(idx_uv, idx_uv+1).value + x}); rsq2.set(idx_vu, {rsq2.prod(idx_vu, idx_vu+1).value - x}); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n;cin>>n; weighted_euler_tour wet(n); rep(i,0,n-1){ ll u,v,w; cin>>u>>v>>w; u--;v--; wet.add_edge(u,v,w); } wet.dfs(0); ll stc=-infl,si=-1; rep(i,0,n){ ll s=wet.dist(0,i); if(s>stc){ stc=s; si=i; } } ll ans=-infl; rep(i,0,n){ ll s=wet.dist(si,i); ans=max(ans,s); } cout<