#include "towns.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <bits/stdc++.h>
#include <time.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=1e6+10,LOG=17,mod=1e9+7;
int block = 340, timer = 0;
const double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9+10;
#define y1 yy
#define prev pre
#define pii pair <int, int>
int n, have, dist[500][500], cnt;
vector <pair <pii, int> > edges;
vector <pii> edge[maxn];
int getdist(int v, int u)
{
if(v == u) return 0;
if(dist[v][u] != -1) return dist[v][u];
dist[v][u] = getDistance(v, u);
dist[u][v] = dist[v][u];
return dist[v][u];
}
void solve(int pred, int V, vector <pii> ver)
{
// cout << "SOLVE " << pred << " " << V << endl;
// for(auto i : ver) cout << i.f << " ";
// cout << endl;
int fi = ver.back().f;
int d1 = ver.back().s;
ver.pop_back();
vector <pii> first, second;
first.pb({fi, d1});
int mn = inf;
while(ver.size())
{
int v = ver.back().f;
int d2 = ver.back().s;
ver.pop_back();
if((d1+d2-getdist(fi, v)) / 2 < mn)
{
// cout << " " << v << " " << d2 << " " << (d1+d2-getdist(fi, v))/2 << endl;
mn = (d1+d2-getdist(fi, v)) / 2;
while(second.size())
{
first.pb(second.back());
second.pop_back();
}
second.pb({v, d2});
}
else
if((d1+d2-getdist(fi, v)) / 2 == mn)
{
second.pb({v, d2});
}
else
{
first.pb({v, d2});
}
}
FOR(0, i, first.size())
{
first[i].s -= mn;
}
FOR(0, i, second.size())
{
second[i].s -= mn;
}
edges.pb({{pred, V}, mn});
if(first.size() == 1)
edges.pb({{first[0].f, V}, first[0].s});
else
solve(V, ++cnt, first);
if(second.size() == 1)
edges.pb({{second[0].f, V}, second[0].s});
else
solve(V, ++cnt, second);
}
int sz[maxn], deep[maxn];
ll mxdist[maxn];
void dfs(int v, int pred)
{
if(edge[v].size() == 1)
sz[v] = 1;
mxdist[v] = 0;
for(auto to : edge[v])
{
if(to.f == pred) continue;
deep[to.f] = deep[v] + to.s;
dfs(to.f, v);
mxdist[v] = max(mxdist[v], mxdist[to.f] + to.s);
sz[v] += sz[to.f];
}
int ok = 1;
for(auto to : edge[v])
{
if(to.f == pred)
{
if(n - sz[v] > n / 2) ok = 0;
}
else
{
if(sz[to.f] > n / 2) ok = 0;
}
}
if(ok) have = 1;
}
ll dpup[maxn];
void dfs2(int v, int pred = -1)
{
vector <ll> pref(edge[v].size()), suff(edge[v].size());
pref[0] = (edge[v][0].f == pred ? 0 : mxdist[edge[v][0].f] + edge[v][0].s);
FOR(1, i, edge[v].size())
{
pref[i] = pref[i - 1];
if(edge[v][i].f == pred) continue;
pref[i] = max(pref[i], mxdist[edge[v][i].f] + edge[v][i].s);
}
suff[(int)edge[v].size() - 1] = (edge[v].back().f == pred ? 0 : mxdist[edge[v].back().f] + edge[v].back().s);
for(int i = (int)edge[v].size() - 2; i >= 0; --i)
{
suff[i] = suff[i + 1];
if(edge[v][i].f == pred) continue;
suff[i] = max(suff[i], mxdist[edge[v][i].f] + edge[v][i].s);
}
FOR(0, i, edge[v].size())
{
pii to = edge[v][i];
if(to.f == pred) continue;
dpup[to.f] = to.s+max({dpup[v], (i>0?pref[i-1]:0), (i+1<(int)edge[v].size()?suff[i+1]:0)});
dfs2(to.f, v);
}
}
int hubDistance(int n, int sub)
{
have = 0;
forn(0, i, n-1)
{
forn(0, j, n-1)
{
dist[i][j] = -1;
}
}
edges.clear();
cnt = n-1;
vector <pii> vec;
forn(1, i, n-1)
{
vec.pb({i, getdist(0, i)});
}
solve(0, ++cnt, vec);
forn(0, i, cnt) edge[i].clear();
for(auto i : edges)
{
edge[i.f.f].pb({i.f.s, i.s});
edge[i.f.s].pb({i.f.f, i.s});
}
deep[0] = 0;
dfs(0, -1);
dfs2(0);
int res = 0;
forn(n, i, cnt)
{
if(max(dpup[i], mxdist[i]) > res) res = max(dpup[i], mxdist[i]);
}
return res * (have ? 1 : -1);
}
/*
1 1
4
0 35 44 31
35 0 29 16
44 29 0 21
31 16 21 0
*/
