BZOJ3451:Tyvj1953 Normal 树分治+期望+FFT

思路:

考虑当\(i\)为重心时,\(j\)在\(i\)的子树中会产生\(1\)的贡献.发生这种情况当且仅当\(i\)是原来的树中从\(i\)到\(j\)的路径上所有的点中第一个删除的点.而由于随机删除我们发现概率为:

\[p=\frac{1}{dist(i,j)+1}\]

由于贡献为\(1\),那么期望贡献就是\(1*p\).

也就是说我们要计算对于每个点为重心时,其余所有点对这个点的贡献.

我们可以暴力枚举,这样是\(O(n^2)\)的.

另一种思路是利用树分治,每次只处理经过重心的路径.

考虑合并两颗子树,暴力合并是\(O(n^2)\),我们利用fft优化求卷积可以做到\(O(nlogn)\).

因此总的时间复杂度为\(O(nlog^2{n})\).

(比较简略,具体看代码)

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=((S=buf)+fread(buf,1,L,stdin));if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';
        while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    template<typename T>inline void Get(T&x,T&y){
        Get(x),Get(y);
    }
}
 
#define INF 0x3f3f3f3f
 
#define N 30010
typedef double f2;
 
static const f2 pi=acos(-1);
struct Cpx{
    f2 x,y;
    Cpx(){}
    Cpx(f2 _x,f2 _y):x(_x),y(_y){}
    Cpx operator+(const Cpx&B)const{return Cpx(x+B.x,y+B.y);}
    Cpx operator-(const Cpx&B)const{return Cpx(x-B.x,y-B.y);}
    Cpx operator*(const f2&p)const{return Cpx(p*x,p*y);}
    Cpx operator/(const f2&p)const{return Cpx(x/p,y/p);}
    Cpx operator*(const Cpx&B)const{return Cpx(x*B.x-y*B.y,x*B.y+y*B.x);}
    inline void operator+=(const Cpx&B){x+=B.x,y+=B.y;}
    inline void operator-=(const Cpx&B){x-=B.x,y-=B.y;}
    inline void operator*=(const f2&p){x*=p,y*=p;}
    inline void operator/=(const f2&p){x/=p,y/=p;}
    inline void operator*=(const Cpx&B){f2 _x=x*B.x-y*B.y,_y=x*B.y+y*B.x;x=_x,y=_y;}
    inline void operator=(const f2&p){x=p,y=0;}
}A[32768],B[32768];
inline void fft(Cpx A[],int n,int rev){
    register int i,j,k;for(i=k=0;i<n;++i){if(i<k)swap(A[i],A[k]);for(j=n>>1;(k^=j)<j;j>>=1);}
    Cpx w,wn,t;
    for(k=2;k<=n;k*=2)
        for(wn=Cpx(cos(2*pi/k),rev*sin(2*pi/k)),i=0;i<n;i+=k)
            for(w=1,j=0;j<k/2;++j,w*=wn)
                t=w,t*=A[i+j+k/2],A[i+j+k/2]=A[i+j]-t,A[i+j]+=t;
    if(rev==-1)for(i=0;i<n;++i)A[i]/=n;
}
 
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
struct Array{
    int a[N],t[N];
    inline int get(int x,int tclock){
        if(t[x]!=tclock)return t[x]=tclock,a[x]=0;
        return a[x];
    }
    inline void modify(int x,int add,int tclock){
        if(t[x]!=tclock)t[x]=tclock,a[x]=0;
        a[x]+=add;
    }
}dep,now;int tclock,tclock2;
 
f2 res;
 
bool ban[N];
int siz[N];
int Minmaxsiz,center;
inline void Getcenter(int x,int fa,int Treesiz){
    siz[x]=1;int Maxsiz=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa&&!ban[end[j]])
        Getcenter(end[j],x,Treesiz),siz[x]+=siz[end[j]],Maxsiz=max(Maxsiz,siz[end[j]]);
    if((Maxsiz=max(Maxsiz,Treesiz-siz[x]))<Minmaxsiz)Minmaxsiz=Maxsiz,center=x;  
}
void dfs(int x,int fa,int d){
    siz[x]=1;
    res+=1/(d+1.0);
    now.modify(d,1,tclock2);
    for(int j=head[x];j;j=next[j])if(end[j]!=fa&&!ban[end[j]])
        dfs(end[j],x,d+1),siz[x]+=siz[end[j]];
}
inline void calc(int x,int Treesiz){
    if(Treesiz==1)return;
    Minmaxsiz=INF,Getcenter(x,-1,Treesiz),ban[center]=1;
    ++tclock;
    int presiz=0;
    for(int j=head[center];j;j=next[j])if(!ban[end[j]]){
        ++tclock2,dfs(end[j],center,1);
        int l;for(l=1;l<presiz+siz[end[j]]+2;l<<=1);
        for(int i=0;i<l;++i)A[i]=Cpx(0,0),B[i]=Cpx(0,0);
        for(int i=1;i<=presiz;++i)A[i]=Cpx(dep.get(i,tclock),0);
        for(int i=1;i<=siz[end[j]];++i)B[i]=Cpx(now.get(i,tclock2),0);
        fft(A,l,1),fft(B,l,1);
        for(int i=0;i<l;++i)A[i]*=B[i];
        fft(A,l,-1);
        for(int i=1;i<=presiz+siz[end[j]];++i){int t=(int)(A[i].x+.5);res+=t/(i+1.0);}
        for(int i=1;i<=siz[end[j]];++i)
            dep.modify(i,now.get(i,tclock2),tclock);
        presiz+=siz[end[j]];
    }
    for(int j=head[center];j;j=next[j])if(!ban[end[j]])calc(end[j],siz[end[j]]);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    int n;Fio::Get(n);
    register int i,j;int a,b;for(i=1;i<n;++i)Fio::Get(a,b),make(++a,++b);
    calc(1,n);
    printf("%.4lf\n",res*2+n);
    return 0;
}