#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef map<ll, ll> mp;
typedef pair<ll, ll> pll;
typedef queue<ll> qi;
typedef vector<ll> vi;
typedef vector <vi> vvi;
typedef vector <pll> vpl;
typedef vector <string> vs;
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define F first
#define S second
#define pb push_back
#define all(x) begin(x), end(x)
void setIO(string name = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
if ((ll)(name.size())) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
#define MAXN 100001
ll br=0, t=1, sl=-1;
vector<pll> adj[MAXN];
ll comp[MAXN],dist[MAXN];
ll tin[MAXN], to[MAXN],fenw[MAXN+1];
vi nds[MAXN];
vi answ;
void dfs(ll nd, ll pr){
comp[nd]=br;
nds[br].pb(nd);
for (pll par: adj[nd]){
ll s=par.F, w=par.S;
if(s==pr) continue;
dist[s]=dist[nd]+w;
dfs(sl, nd);
}
}
void dfs1(ll nd, ll pr) {
tin[nd]=t;
t++;
for (pll par: adj[nd]) {
ll s=par.F, w=par.S;
if (s == pr) continue;
dist[s] = dist[nd] + w;
dfs1(s, nd);
}
to[nd]=t-1;
}
void update(ll pos, ll val) {
for (ll i=pos; i <=t + 1; i+=i&(-i)) fenw[i] += val;
}
ll query(ll pos) {
ll sum=0;
for (ll i=pos; i>0; i-=i&(-i)) sum+=fenw[i];
return sum;
}
void resi(ll comp, ll n) {
ll maxdist=0, maxnode=nds[comp][0];
for (ll node: nds[comp]) {
if (dist[node] > maxdist) {
maxdist=dist[node];
maxnode=node;
}
}
t=1; dist[maxnode]=0; dfs1(maxnode, 0);
ll len=0, sol=len;
for (ll i=1; i<=t+1; i++) fenw[i]=0;
for (ll node: nds[comp]) {
len=max(len, dist[node]);
sol=len;
}
for (ll node: nds[comp]) {
if (dist[node] == len) update(tin[node], 1);
}
for (ll node: nds[comp]) {
ll value=max(dist[node], len-dist[node]);
if (value >= sol) continue;
if (value == dist[node]) {
sol=min(sol, value);
continue;
}
ll broj=query(to[node]) - query(tin[node]-1);
if (broj > 0) sol=min(sol, value);
}
answ.pb(sol);
}
ll travelTime(ll n, vi u, vi v, vi w) {
for (ll i=0; i<n-1; i++) {
adj[u[i]].pb({v[i], w[i]});
adj[v[i]].pb({u[i], w[i]});
}
for (ll i=0; i<n; i++) {
if (comp[i] == 0) {
br++;
dfs(i, -1);
}
}
for (ll i=1; i<=br; i++) resi(i, n);
ll ans=0;
for (ll x: answ) ans+=x;
return ans;
}
