https://www.cnblogs.com/GXZlegend/p/8611948.html
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
using namespace std; const int N=;
const double pi=acos(-.);
int n,u,v,S,rt,tot,cnt,mx,d[N],q[N],rev[N];
int vis[N],sz[N],f[N],h[N],to[N<<],nxt[N<<];
double ans,num[N];
void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } struct C{ double x,y; }a[N];
C operator +(const C &a,const C &b){ return (C){a.x+b.x,a.y+b.y}; }
C operator -(const C &a,const C &b){ return (C){a.x-b.x,a.y-b.y}; }
C operator *(const C &a,const C &b){ return (C){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x}; } void find(int x,int fa){
sz[x]=; f[x]=;
For(i,x) if (!vis[k=to[i]] && k!=fa)
find(k,x),sz[x]+=sz[k],f[x]=max(f[x],sz[k]);
f[x]=max(f[x],S-sz[x]);
if (f[x]<f[rt]) rt=x;
} void get(int x,int fa){
q[++tot]=d[x];
For(i,x) if (!vis[k=to[i]] && k!=fa) d[k]=d[x]+,get(k,x);
} void DFT(C a[],int n,int f){
for (int i=; i<n; i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
for (int i=; i<n; i<<=){
C wn=(C){cos(pi/i),f*sin(pi/i)};
for (int p=i<<,j=; j<n; j+=p){
C w=(C){,};
for (int k=; k<i; k++,w=w*wn){
C x=a[j+k],y=w*a[i+j+k]; a[j+k]=x+y; a[i+j+k]=x-y;
}
}
}
if (f==-) for (int i=; i<n; i++) a[i].x/=n;
} void calc(int fl){
int n=,L=; mx=;
rep(i,,tot) mx=max(mx,q[i]);
for (; n<=mx<<; n<<=) L++;
for (int i=; i<n; i++) rev[i]=(rev[i>>]>>)|((i&)<<(L-));
for (int i=; i<n; i++) a[i].x=a[i].y=;
rep(i,,tot) a[q[i]].x++;
DFT(a,n,);
for (int i=; i<n; i++) a[i]=a[i]*a[i];
DFT(a,n,-);
rep(i,,*mx) num[i]+=fl*(int)(a[i].x+0.1);
} void work(int x){
vis[x]=; d[x]=tot=; get(x,); calc();
For(i,x) if (!vis[k=to[i]]){
d[k]=; tot=; get(k,); calc(-);
S=sz[k]; rt=; find(k,); work(rt);
}
} int main(){
freopen("bzoj3451.in","r",stdin);
freopen("bzoj3451.out","w",stdout);
scanf("%d",&n);
rep(i,,n) scanf("%d%d",&u,&v),add(u+,v+),add(v+,u+);
S=f[]=n; find(,); work(rt);
rep(i,,n) ans+=num[i-]/i;
printf("%.4lf\n",ans);
return ;
}