Description：

随机选分治中心点分治的期望操作次数。

$1\leqslant n\leqslant 30000$

Solution：

遇到期望的题，一定要考虑利用期望的线性性来对每一个分别求解。

考虑某一个点被计算的次数，会发现： $$ ans=\sum_{i=1}^n\sum_{j=1}^nE[i在点分树中是j的祖先] $$ $i$ 在点分树中是 $j$ 的祖先当且仅当对于一条路径 $i\longleftrightarrow j$ ， $i$ 是第一个被选出来的点，由于选择是随机的，所以这个概率是 $\frac 1{dis(i,j)}$ ，也就是说： $$ ans=\sum_{i=1}^n\sum_{j=1}^n\frac{1}{dis(i,j)} $$ 那我们的问题就变成了要统计树上长度为每个值的路径条数，这个可以点分治 $+FFT$ 。

但是这题复杂度非常玄学，首先点分治有两个写法，一种是每次搜索一棵子树，然后把子树信息和原来信息合并，另一种是直接搜完这棵子树，然后考虑两两之间的贡献，然后减去重复的，这道题的话，如果用第一种方法，那么如果上来是一个 $\frac n 2$ 的链，然后剩下 $\frac n 2$ 棵子树，就被卡成了 $O(n^2\log ^2n)$ ，如果用第二种方法，那么最长的那条链只会被算两次（最开始一次容斥依次），由于最长链长度是 $O(n)$ 的，复杂度就是 $O(n\log^2n)$ 了。

是不是如果复杂度与子树深度有关那就用第二种？

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 30010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int siz[MAXN],d[MAXN],root,s;

bool vis[MAXN];

#define INF 0x3f3f3f3f

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa && !vis[e[i].to])

		{

			getroot(e[i].to,k);

			siz[k] += siz[e[i].to];

			d[k] = max(d[k],siz[e[i].to]);

		}

	}

	d[k] = max(d[k],s - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

#define MAX 70000

struct comp

{

	double r,i;

	comp(double r_ = 0.0,double i_ = 0.0){r = r_;i = i_;}

}f[MAX];

comp operator + (comp a,comp b){return (comp){a.r + b.r,a.i + b.i};}

comp operator - (comp a,comp b){return (comp){a.r - b.r,a.i - b.i};}

comp operator * (comp a,comp b){return (comp){a.r * b.r - a.i * b.i,a.r * b.i + a.i * b.r};}

int rev[MAX];

const double PI = acos(-1);

void FFT(comp f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		comp wn = (comp){cos(-type * 2 * PI / i),sin(-type * 2 * PI / i)};

		for(int j = 0;j < l;j += i)

		{

			comp w = (comp){1,0};

			for(int k = j;k < j + i / 2;++k)

			{

				comp u = f[k],t = w * f[k + i / 2];

				f[k] = u + t;

				f[k + i / 2] = u - t;

				w = w * wn;

			}

		}

	}

	if(type == -1)

	{

		for(int i = 0;i < l;++i)f[i].r /= l;

	}

	return;

}

int maxd;

void dfs(int k,int fa,int dep)

{

	maxd = max(maxd,dep);

	f[dep].r += 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		dfs(e[i].to,k,dep + 1);

	}

	return;

}

int cnt[MAXN];

void calc(int k,int type,int dep)

{

	maxd = 0;

	dfs(k,0,dep);

	int l = 0,len = 1;

	for(;len <= maxd * 2;len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	FFT(f,len,1);

	for(int i = 0;i < len;++i)f[i] = f[i] * f[i];

	FFT(f,len,-1);

	for(int i = 0;i < len;++i)cnt[i] = cnt[i] + type * int(f[i].r + 0.5);

	for(int i = 0;i < len;++i)f[i] = (comp){0,0};

	return;

}

void divide(int k)

{

	vis[k] = true;

	calc(k,1,0);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		calc(e[i].to,-1,1);

		root = 0;s = siz[e[i].to];

		getroot(e[i].to,0);

		divide(root);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		++a;++b;

		add(a,b);

	}

	root = 0;s = n;d[0] = INF;

	getroot(1,0);

	divide(root);

	double ans = 0.0;

	for(int i = 1;i <= n;++i)

	{

		ans = ans + 1.0 / i * cnt[i - 1];

	}

	printf("%.4lf\n",ans);

	return 0;

}