sxczf's Blog

#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 100005
using namespace std;
struct node{double x,y;}a[maxn*4],b[maxn*4],w[2][maxn*4];
inline node operator +(node a,node b){return (node){a.x+b.x,a.y+b.y};}
inline node operator -(node a,node b){return (node){a.x-b.x,a.y-b.y};}
inline node operator *(node a,node b){return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
int c,e,f[maxn],g,h,i,j,k,l,m,n,N,All,root,Max,tot;
double ans;
int rev[maxn*4],way[maxn*2],next[maxn*2],last[maxn];
int data[maxn],d[maxn],can[maxn],size[maxn];
int F[maxn],p[maxn];

inline void make(int a,int b){
	way[++tot]=b;next[tot]=last[a];last[a]=tot;
	way[++tot]=a;next[tot]=last[b];last[b]=tot;
}

inline void pre(){
	for(int i=0;i<N;i++){
		int j=1,x=i,y=0;
		for(;j<N;j<<=1,x>>=1)(y<<=1)|=(x&1);
		rev[i]=y;
	}
	for(int i=0;i<N;i++){
		double e=2.0*acos(-1)*i/N;
		w[0][i]=(node){cos(e),sin(e)};
		w[1][i]=(node){cos(e),-sin(e)};
	}
}

inline void FFT(node *A,int f){
	for(int i=0;i<N;i++)if(rev[i]>i)swap(A[i],A[rev[i]]);
	for(int i=1;i<N;i<<=1)
	for(int j=0,t=N/(i<<1);j<N;j+=(i<<1))
	for(int k=l=0;k<i;k++,l+=t){
		node p=A[j+k+i]*w[f][l];
		node q=A[j+k];
		A[j+k]=q+p;
		A[j+k+i]=q-p;
	}
	if(f)for(int i=0;i<N;i++)A[i].x/=N;
}

void geta(int x,int fa){
	data[++data[0]]=d[x];
	Max=max(Max,d[x]);
	for(int i=last[x];i;i=next[i])if(way[i]!=fa&&!can[way[i]]){
		int s=way[i];
		d[s]=d[x]+1;
		geta(s,x);
	}
}

double calc(int x,int k){
	d[x]=k;data[0]=0;Max=0;geta(x,-1);
	for(N=1;N<=Max;N<<=1);N<<=1;
	for(int i=0;i<N;i++)a[i]=(node){0,0};
	for(int i=1;i<=data[0];i++)a[data[i]].x+=1.0;
	
	pre();FFT(a,0);FFT(b,0);
	for(int i=0;i<N;i++)a[i]=a[i]*a[i];
	FFT(a,1);
	double ans=0;
	for(int i=1;p[i]<=Max*2;i++)
	ans+=a[p[i]].x;
	return ans;
}

void getr(int x,int fa){
	size[x]=1;f[x]=0;
	for(int i=last[x];i;i=next[i])if(way[i]!=fa&&!can[way[i]]){
		int s=way[i];
		getr(s,x);
		size[x]+=size[s];
		if(size[s]>f[x])f[x]=size[s];
	}
	if(All-size[x]>f[x])f[x]=All-size[x];
	if(f[x]<f[root])root=x;
}

void work(int x){
	ans+=calc(x,0);can[x]=1;
	for(int i=last[x];i;i=next[i])
	if(!can[way[i]]){
		int s=way[i];
		ans-=calc(s,1);
		All=size[s];f[root=0]=n+1;
		getr(s,-1);
		work(root);
	}
}

void Pre(){
	for(i=2;i<=maxn;i++)if(!F[i]){
		p[++p[0]]=i;
		for(j=2*i;j<=maxn;j+=i)F[j]=1;
	}
}

int main(){
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d",&c,&e);
		make(c,e);
	}
	Pre();
	All=n;f[root=0]=n+1;
	getr(1,-1);
	work(root);
	double Ans=1.0*ans/n/(n-1);
	printf("%.9lf",Ans);
	return 0;
}