namespace TreeBasic
{
int n;
vector<int> G[MAX];
int dep[MAX],dps;
void Diameter(int now,int father)
{
dep[now]=dep[father]+1;
if(dep[now]>dep[dps]) dps=now;
for(auto to:G[now]) if(to!=father) Diameter(to,now);
}
inline int Diameter() {Diameter(1,0),Diameter(dps,0); return dep[dps];}
int siz[MAX],wgt[MAX],ctr[2];
void Centroid(int now,int father)
{
siz[now]=1,wgt[now]=0;
for(auto to:G[now]) if(to!=father) Centroid(to,now),siz[now]+=siz[to],cmax(wgt[now],siz[to]);
cmax(wgt[now],n-wgt[now]);
if(wgt[now]<=n/2) ctr[ctr[0]!=0]=now;
}
inline void Centroid() {Centroid(1,0);}
}