[BZOJ3451]Normal - A-Failure的博客

题目

Description

某天WJMZBMR学习了一个神奇的算法：树的点分治！

这个算法的核心是这样的：

消耗时间=0

Solve(树 a)

消耗时间 += a 的大小

如果 a 中只有 1 个点

退出

否则在a中选一个点x，在a中删除点x

那么a变成了几个小一点的树，对每个小树递归调用Solve

我们注意到的这个算法的时间复杂度跟选择的点x是密切相关的。

如果x是树的重心，那么时间复杂度就是O(nlogn)

但是由于WJMZBMR比较傻逼，他决定随机在a中选择一个点作为x！

Sevenkplus告诉他这样做的最坏复杂度是O(n^2)，但是WJMZBMR就是不信>_<。。。

于是Sevenkplus花了几分钟写了一个程序证明了这一点。。。你也试试看吧^_^

现在给你一颗树，你能告诉WJMZBMR他的傻逼算法需要的期望消耗时间吗？（消耗时间按在Solve里面的那个为标准）

Input

第一行一个整数n，表示树的大小接下来n-1行每行两个数a,b，表示a和b之间有一条边注意点是从0开始标号的

Output

一行一个浮点数表示答案四舍五入到小数点后4位如果害怕精度跪建议用long double或者extended

Sample Input

3
0 1
1 2

Sample Output

5.6667

HINT

n<=30000

题解

如果点$i$能对点$j$产生贡献，那么$i$肯定在$j$的点分树里，用$P(i,j)$表示选了$j$下一次就选的$i$的概率，则答案为$\sum_{i=1}^{n}\sum_{j=1}^{n}P(i,j)$

$P(i,j)$就是$\frac{1}{dis(i,j)}$了，这样可以点分治处理每个点子树的贡献，用$FFT$优化计算

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std;
const int MAX=1e5+5;
const double Pi=acos(-1.0);
struct Complex{
	double x,y;
	Complex(double X=0,double Y=0) {x=X,y=Y;}
}a[MAX],b[MAX];
struct p{
	int x,y;
}c[MAX];
int n,num,rt,Sum,maxn,lim=1,L,tot;
double ans;
int h[MAX],d[MAX],siz[MAX],Num[MAX],f[MAX],R[MAX];
bool use[MAX];
Complex operator+ (Complex x,Complex y) {return Complex(x.x+y.x,x.y+y.y);}
Complex operator- (Complex x,Complex y) {return Complex(x.x-y.x,x.y-y.y);}
Complex operator* (Complex x,Complex y) {return Complex(x.x*y.x-x.y*y.y,x.y*y.x+x.x*y.y);}
void FFT(Complex *A,int tt=1)
{
	for(int i=0;i<lim;++i)
	  if(i<R[i]) swap(A[i],A[R[i]]);
	for(int i=1;i<lim;i<<=1)
	  {
	  	Complex w1=Complex(cos(Pi/i),tt*sin(Pi/i));
	  	for(int l=i<<1,j=0;j<lim;j+=l)
	  	  {
	  	  	Complex w=Complex(1,0),x,y;
	  	  	for(int k=0;k<i;++k,w=w*w1)
	  	  	  x=A[j+k],y=w*A[i+j+k],A[j+k]=x+y,A[i+j+k]=x-y;
		  }
	  }
}
void add(int x,int y)
{
	c[++num]=(p){h[x],y},h[x]=num;
	c[++num]=(p){h[y],x},h[y]=num;
}
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void Dfs(int x,int fa,int D)
{
	maxn=max(maxn,D),d[++tot]=D;
	for(int i=h[x];i;i=c[i].x)
	  if(!use[c[i].y]&&(c[i].y^fa)) Dfs(c[i].y,x,D+1);
}
double ask(int x,int D=0)
{
	tot=maxn=0;
	double ans=0;
	Dfs(x,0,D);
	lim=1,L=0;
	while(lim<=2*maxn) lim<<=1,++L;
	for(int i=0;i<=lim;++i)
	  a[i]=Complex(0,0),b[i]=Complex(0,0);
	for(int i=1;i<=tot;++i)
	  ++a[d[i]].x,++b[d[i]].x;
	R[0]=0;
	for(int i=0;i<lim;++i)
	  R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
	FFT(a),FFT(b);
	for(int i=0;i<=lim;++i)
	  a[i]=a[i]*b[i];
	FFT(a,-1);
	for(int i=0;i<=2*maxn;++i)
	  ans+=1.0/(i+1)*int(a[i].x/lim+0.5);
	return ans;
}
void GET_ROOT(int x,int fa=0)
{
	f[x]=0,siz[x]=1;
	for(int i=h[x];i;i=c[i].x)
	  if(!use[c[i].y]&&(c[i].y^fa))
	  {
	  	GET_ROOT(c[i].y,x),siz[x]+=siz[c[i].y];
	  	f[x]=max(f[x],siz[c[i].y]);
	  }
	f[x]=max(f[x],Sum-siz[x]);
	if(f[x]<f[rt]) rt=x;
}
void dfs(int x=rt)
{
	ans+=ask(x),use[x]=1;
	for(int i=h[x],xsum=Sum;i;i=c[i].x)
	  if(!use[c[i].y])
	  {
	  	if(siz[x]>siz[c[i].y]) Sum=siz[c[i].y];
	  	else Sum=xsum-siz[x];
	  	ans-=ask(c[i].y,1),f[rt=0]=Sum,GET_ROOT(c[i].y,x),dfs();
	  }
}
int main()
{
	n=read();
	for(int i=1;i<n;++i)
	  add(read()+1,read()+1);
	return Sum=f[rt]=n,GET_ROOT(1),dfs(),printf("%.4lf",ans),0;
}

题目