记直径为\((x,y)\)，则有以下做法：
-
利用直径的经典做法，可以\(3n\)次询问得到\(x,y\)和其余点到\(x,y\)的距离
设直径上距离\(i\)最近的点为\(k\)，已知\(x,y,i\)两两距离，即可解出\(k\)到\(x,y,i\)的距离
-
注意到\(r(k)=\max\{dis(k,x),dis(k,y)\}\)，即中心城市恰为所有直径上最靠近中心的点
同时，由于度数\(\ge 3\)，其必然作为前者的某个\(k\)，进而即可得到\(R\)和\(r(k)\)
-
检验\(r(k)=R\)删除后是否平衡，其中包含\(x\)或\(y\)的两个连通块大小易得
对于内部两点\(a,b\)，其在同一个连通块内当且仅当\(dis(k,a)+dis(k,b)\ne dis(a,b)\)
注意到\(>\lfloor\frac{n}{2}\rfloor\)的必然为绝对众数，用经典做法可以\(2n\)次询问得到众数并检验
上述做法的总询问次数为\(5n-O(1)\)，下面考虑优化：
-
\((x,y)\)并不一定要是直径，仅需保证所有中心城市均在其路径上即可
具体的，取距离\(0\)最远的一点\(z\)，取\((x,y)=(0,z)\)即可，询问次数降为\(2n-3\)
注意此时的\(r(k)\)不能仅考虑\(x,y\)，需枚举所有点求\(\max dis(k,i)\)
-
在得到众数的过程中，将其按众数的变化分为若干段，每段即等量的与该段众数相同和不同的数
得到众数时，询问次数为\(n-段数\)；检验时，相同的部分仅需询问一次，询问次数为\(\lfloor\frac{n}{2}\rfloor+段数\)
总询问次数为\(3n+\lfloor\frac{n}{2}\rfloor-O(1)\le \lceil\frac{7n}{2}\rceil\)
#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
const int N=200,M=1000005;
int n,x,y,R,D[N][N],dx[N],dy[N],d[N],pos[N];
vector<int>v[M];
int dis(int x,int y){
if (x==y)return 0;
if (x>y)swap(x,y);
if (!D[x][y])D[x][y]=getDistance(x,y);
return D[x][y];
}
int hubDistance(int _n,int tp){
n=_n,x=0,y=1;
memset(D,0,sizeof(D));
for(int i=0;i<n;i++)dx[i]=dis(x,i);
for(int i=2;i<n;i++)
if (dx[y]<dx[i])y=i;
for(int i=0;i<n;i++)dy[i]=dis(y,i);
for(int i=0;i<M;i++)v[i].clear();
for(int i=0;i<n;i++){
d[i]=(dx[i]+dy[i]-dx[y]>>1);
pos[i]=(dx[i]+dx[y]-dy[i]>>1);
if ((i!=x)&&(i!=y))v[pos[i]].push_back(i);
}
R=1e9;
for(int i=0;i<=dx[y];i++)
if (!v[i].empty()){
int s=0;
for(int j=0;j<n;j++)s=max(s,d[j]+abs(i-pos[j]));
R=min(R,s);
}
int sz=1;
for(int i=0;i<=dx[y];i++){
if (!v[i].empty()){
int s=0;
for(int j=0;j<n;j++)s=max(s,d[j]+abs(i-pos[j]));
if ((s==R)&&(sz<=(n>>1))&&(n-sz-v[i].size()<=(n>>1))){
int k,cnt=0;
for(int j=0;j<v[i].size();j++){
if (!cnt)k=v[i][j],cnt=1;
else{
if (dis(k,v[i][j])!=d[k]+d[v[i][j]])cnt++;
else cnt--;
}
}
int k0=k,cnt0=cnt=0;
for(int j=0;j<v[i].size();j++){
if (!cnt){
k=v[i][j],cnt=1;
if (dis(k,k0)!=d[k]+d[k0])cnt0++;
}
else{
if (dis(k,v[i][j])!=d[k]+d[v[i][j]]){
cnt++;
if (dis(k,k0)!=d[k]+d[k0])cnt0++;
}
else{
cnt--;
if (dis(k0,v[i][j])!=d[k0]+d[v[i][j]])cnt0++;
}
}
}
if (cnt0<=(n>>1))return R;
}
}
sz+=v[i].size();
}
return -R;
}