#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> dist0;
int a=-1;
vector<int> dista;
int b=-1;
vector<int> distb;
int Distance(int i, int j){
if(j<i) swap(i, j);
if(i==0) return dist0[j];
if(i==a) return dista[j];
if(i==b) return distb[j];
if(j==a) return dista[i];
if(j==b) return distb[i];
return getDistance(i, j);
}
bool balancedSlow(int n, int r, int diameter, map<int, vector<int> >& group){
bool balanced_hub=false;
int cntleft=1;
for(auto [x, g]: group){
if(max(x, diameter-x)!=r){ //no hub
continue;
}
int cntright = n - cntleft - (int)g.size();
if(cntleft>n/2 || cntright>n/2) continue;
vector<bool> vis(n, false);
int open = (int)g.size();
bool balanced=true;
while(open > n/2){
int v=g.back(); g.pop_back();
if(vis[v]){
continue;
}
vis[v]=true;
int size=1;
for(auto u: g){
int d = Distance(v, u);
if(d < dista[v]-x + dista[u]-x){ //same component
vis[u]=true;
size++;
}
}
if(size > n/2){
balanced = false;
break;
}
open -= size;
}
if(balanced){
balanced_hub = true;
break;
}
cntleft += (int)group.size();
}
return balanced_hub;
}
bool balanced4(int n, int r, int diameter, map<int, vector<int> >& group){
int left=1;
for(auto [x, g]: group){
if(r!= max(x, diameter-x)){ //no hub
left += g.size();
continue;
}
int gsize=g.size();
int right=n-left-gsize;
if(left<=n/2 && right<=n/2 && gsize<=n/2){
return true;
}
left += gsize;
}
assert(left==n-1);
return false;
}
int hubDistance(int n, int sub) {
//find diameter
dist0.assign(n, 0);
a=1;
for(int i=1; i<n; i++){
dist0[i] = getDistance(0, i);
if(dist0[i]>dist0[a]){
a=i;
}
}
b=0;
dista.assign(n, 0);
dista[0] = dist0[a];
for(int i=1; i<n; i++){
if(i==a) continue;
dista[i] = getDistance(a, i);
if(dista[i] > dista[b]){
b=i;
}
}
distb.assign(n, 0);
distb[0] = dist0[b];
distb[a] = dista[b];
for(int i=1; i<n; i++){
if(i==a || i==b) continue;
distb[i] = getDistance(b, i);
}
int diameter = dista[b];
//group the leafes
vector<int> dleft(n); dleft[a]=0; dleft[b]=diameter;
vector<int> ddiam(n); ddiam[a]=ddiam[b]=0;
map<int, vector<int> > group;
for(int i=0; i<n; i++){
if(i==a || i==b) continue;
ddiam[i] = (dista[i]+distb[i] - diameter)/2;
dleft[i] = dista[i]-ddiam[i];
group[dleft[i]].push_back(i);
}
//compute r
int r=diameter;
for(auto [x, g]: group){
r = min(r, max(x, diameter-x));
}
bool balanced=true;
if(2<sub){
balanced=balanced4(n, r, diameter, group);
}
if(balanced){
return r;
}
return -r;
}
