#include "towns.h"
#include <bits/stdc++.h>
#define maxn 115
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int nodeA, nodeB, diameter, condition = 0, cachedA[maxn], cachedB[maxn];
bool cmp(int u, int v) {
int distance_to_mid_point = 0,
distance_to_lca = 0;
int A_minus_B = cachedA[u] - cachedB[u],
A_plus_B = diameter;
int mid_point_to_A = (A_plus_B + A_minus_B) / 2;
distance_to_mid_point = cachedA[u] - mid_point_to_A;
int u_minus_v = cachedA[u] - cachedA[v];
int u_plus_v = getDistance(u, v);
distance_to_lca = (u_minus_v + u_plus_v) / 2;
return (distance_to_lca < distance_to_mid_point);
}
void solve_for_node(int N, int disA, int disB) {
vector<int> Mid; int SzL = 0, SzR = 0;
for (int i = 0; i < N; i++) {
int dA = (diameter + (cachedA[i] - cachedB[i])) / 2;
if (dA == disA) Mid.emplace_back(i);
else if (dA < disA) ++SzL;
else ++SzR;
}
int sz = Mid.size();
int pos = 0;
for (int i = 1, cnt = 0; i < sz; i++) {
if (cmp(Mid[i], Mid[pos])) ++cnt;
else --cnt;
if (cnt <= 0) {
cnt = 1;
pos = i;
}
}
int dem = 0;
for (int i = 0; i < sz; i++)
if (cmp(Mid[i], Mid[pos])) ++dem;
if (dem > (N/2) || SzL > (N/2) || SzR > (N/2)) return;
condition = 1;
}
int hubDistance(int N, int sub) {
condition = 0;
nodeA = 0; nodeB = 0; int mx = -1;
for (int i = 1; i < N; i++) {
int t = getDistance(0, i);
if (mx < t) {
nodeA = i;
mx = t;
}
}
mx = -1;
cachedA[nodeA] = 0;
for (int i = 0; i < N; i++) {
int t = cachedA[i] = getDistance(nodeA, i);
if (i != nodeA && mx < cachedA[i]) {
mx = cachedA[i];
nodeB = i;
}
}
int ans = INT_MAX, tong = diameter = mx;
vector<ii> possible;
cachedB[nodeB] = 0;
cachedB[nodeA] = diameter;
for (int i = 0; i < N; i++)
if (i != nodeA && i != nodeB) {
int hieu = cachedA[i] - (cachedB[i] = getDistance(nodeB, i)),
disA = (tong + (cachedA[i] - cachedB[i])) / 2,
disB = (tong + (cachedB[i] - cachedA[i])) / 2;
if (hieu < 0) hieu = -hieu;
if (ans > (tong+hieu)/2) {
ans = (tong+hieu)/2;
possible.clear();
possible.emplace_back(disA, disB);
} else if (ans == (tong+hieu)/2) {
possible.emplace_back(disA, disB);
}
}
sort(possible.begin(), possible.end());
possible.erase(unique(possible.begin(), possible.end()), possible.end());
for (auto [u, v] : possible) solve_for_node(N, u, v);
return condition ? ans : -ans;
}
