#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
const int INF = 1e9 + 5;
const ll LINF = 4e18;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int((x).size()))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rev(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define f first
#define s second
template<class T> bool chmin(T& a, const T&b) {return b < a ? a = b, 1 : 0;}
template<class T> bool chmax(T& a, const T&b) {return a < b ? a = b, 1 : 0;}
#ifdef LOCAL
#define dbg(x) cerr << #x << " = " << x
#else
#define dbg(x)
#endif
struct DSU {
int n; vi par, siz, leaf;
DSU(int N = 0) : n(N), par(n, -1), siz(n, 1), leaf(n, -1) {}
int find(int v) {return par[v] == -1 ? v : par[v] = find(par[v]);}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a != b) {
// if (siz[a] < siz[b]) swap(a, b);
par[b] = a; siz[a] += siz[b];
if (leaf[a] == -1) leaf[a] = leaf[b];
}
}
void setleaf(int u) {
leaf[find(u)] = u;
}
int get_leaf(int u) {
return leaf[find(u)];
}
};
/*
1. every small town is a leaf
2. 2 nodes are siblings if every distance differs only by a constant value for every node except themselves
*/
int n; bool sub;
vi par_dist, par;
DSU dsu;
int leaf_dist(int i) {
i = dsu.find(i);
int r = 0, u = dsu.get_leaf(i);
while (par_dist[u] != -1 && u != i) {
r += par_dist[u]; u = par[u];
}
u = dsu.get_leaf(i);
// cout << "leaf distance from ";
// if (u < n) cout << u;
// else cout << char('a' + (u-n));
// cout << " (leaf) to ";
// if (i < n) cout << i;
// else cout << char('a' + (i-n));
// cout << " (head) is " << r << "\n";
return r;
}
map<pi, int> cache;
int query(int idx, int jdx) {
int i = dsu.get_leaf(idx), j = dsu.get_leaf(jdx);
int x = -1;
if (cache.count({i, j})) x = cache[{i, j}];
else {
x = cache[{i,j}] = cache[{j,i}] = getDistance(i, j);
}
x -= leaf_dist(idx);
x -= leaf_dist(jdx);
return x;
}
struct edge {
int v, w;
};
int hubDistance(int N, int SUB) {
n = N; sub = SUB > 2;
vector<vector<edge>> G(2*n); int id = n;
vi active(n); par_dist.assign(2*n, -1), par.assign(2*n, -1); iota(all(active), 0);
dsu = DSU(2*n); for (int i = 0; i < n; i++) dsu.setleaf(i);
auto are_siblings = [&](int u, int v) {
bool ok = true, found = false; int dx = 0;
rep(i, 0, n) {
if (dsu.find(i) == dsu.find(u) || dsu.find(i) == dsu.find(v)) continue;
int d1 = query(u, i), d2 = query(v, i);
if (!found) found = true, dx = d1 - d2;
ok = ok && dx == d1 - d2;
if ((d1 - d2) != dx) {
// cout << u << " and " << v << " fail on " << i << "\n";
}
}
return ok;
};
while (sz(active) > 2) {
vi active2; bool found = false;
set<int> used;
rep(idx, 0, sz(active)) {
vi sib(1, active[idx]);
rep(jdx, idx+1, sz(active)) {
int i = active[idx], j = active[jdx];
if (used.count(i) || used.count(j)) continue;
if (!are_siblings(i, j)) continue;
sib.pb(j);
int k = 0; while (k < 2 * n && (dsu.find(k) == i || dsu.find(k) == j)) k++;
int x = query(i, j);
int y = query(i, k);
int z = query(j, k);
int di = 0, dj = 0;
dj = (z + x - y) / 2;
di = x - dj;
par_dist[i] = di; par_dist[j] = dj;
}
if (sz(sib) <= 1) continue;
found = true;
// cout << "merging nodes: ";
// for (auto j : sib) {
// if (j < n) cout << j << " ";
// else cout << char('a' + (j-n)) << " ";
// }
// cout << "into node " << char('a' + (id - n)) << "\n";
for (auto j : sib) {
dsu.unite(id, j);
used.insert(j);
par[j] = id;
// if (j < n) cout << j << " ";
// else cout << char('a' + (j-n)) << " ";
// cout << char('a' + (id-n)) << " " << par_dist[j] << "\n";
}
active2.pb(id++);
}
if (!found) break;
for (auto &x : active) if (!used.count(x)) active2.pb(x);
swap(active, active2);
}
if (active.size() == 2) {
int x = active[0], y = active[1];
int weight = query(x, y);
dsu.unite(x, y);
par[y] = x;
par_dist[y] = weight;
// if (x < n) cout << x << " ";
// else cout << char('a' + (x-n)) << " ";
// if (y < n) cout << y << " ";
// else cout << char('a' + (y-n)) << " ";
// cout << weight << "\n";
}
rep(i, 0, 2*n) if (par[i] != -1) G[i].push_back(edge{par[i], par_dist[i]}), G[par[i]].push_back(edge{i, par_dist[i]});
auto get_r = [&](auto &&self, int u, int p, int dist)->pi {
if (u < n) return {dist, 1};
int r = -INF, subsz = 0, submax = -INF;
for (auto &[v, w] : G[u]) {
if (v == p) continue;
auto res = self(self, v, u, dist + w);
subsz += res.s;
r = max(r, abs(res.f));
submax = max(submax, res.s);
}
if (r == -INF) r = INF;
if (submax <= n/2) r = -r;
return {r, subsz};
};
int R = INF; rep(i, n, 2*n) {
auto r = get_r(get_r, i, -1, 0);
if (abs(r.f) < abs(R)) R = r.f;
}
return R;
}
