题目描述

众所周知，XZY 是一个善于思考的女孩子，她经常发明一些很厉害的算法，比如每次插入后 splay 随机次的 “XZY-splay”，或者随机选取重心的 “XZY 点分治”。

XZY 虽然擅长于发明算法，但是并不擅长证明自己发明的算法的复杂度。所以她拜托了 ABS 来帮忙计算 “XZY 点分治” 的复杂度。

众所周知，ABS 是一个很强的男孩子，他一拍桌子，迅速想出了一种计算对于一棵给定的树运行 “XZY 点分治” 的代价计算方式：

int ans=0;
定义 某种神秘容器 st
void dfs(int x,int fa) {
    ++ans;
    for 与点 x 相连的点 y
        if(!vis[y]&&y!=fa) dfs(y,x);
}
void dfs2(int x,int fa) {
    st.insert(x);
    for 与点 x 相连的点 y
        if(!vis[y]&&y!=fa) dfs2(y,x);
}
void work(int x) {
    vis[x]=1;dfs(x,0);
    for 与点 x 相连的点 y
        if(!vis[y]) st.clear(),dfs2(y,x),work(随机一个 st 中的点);
}
int main() {
    读入一棵树 T
    work(随机一个树上的点);
    输出 ans
}

众所周知，宇宙中最优秀的程序员 ABS 早已经编写好一个真随机数生成器，因此我们可以认为上面这份代码中所有 “随机” 的地方都是真随机的。

ABS 认为，只要再生成一些不同特性的树，例如无旋 triep 或者竹子，然后运行这份代码观察 ans 的输出结果，就可以知道 “XZY 点分治” 的运行效率怎么样了。

XZY 看了之后，欢天喜地，载兴载犇，僮仆欢迎，稚子候门，动手动脚，牛逼哄哄。

而对于处理给定形态的树，“XZY 点分治” 的期望复杂度为运行上述代码输出的 ans 的期望。由于 ABS 很强，所以他要日理万机，非常忙碌，她觉得只要运行以上代码若干次就能够计算期望，非常一几，这个工作就交给你来做了。

输出答案乘以 $n!$并对 $10^9+7$取模的结果。

数据范围

$n \leq 10^5$

题目分析

对于两个点 x 和 y，当 x 作为重心的时候，y 会对答案产生贡献，当且仅当，x 到 y 这条路径上，x 是第一个被选为重心的点。

当 x 和 y 尚且处于同一连通块时，他们及他们路径中间的点被第一个选为重心的概率是相等的，设有 $L$个点，则概率为 $\frac{1}{L}$

设 $d_i$表示树上路径长度为 $i$的点对数有多少，那么答案就是：

$$(\sum _ {i=1}^{n-1} \frac{d _ i}{i})n!$$

所以就是点分治，然后用 FFT 合并子树信息，求出每种长度的路径有多少条即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
typedef long long LL;
typedef double db;
const int mod=1000000007,N=100005,inf=0x3f3f3f3f;
const db pi=acos(-1);
int h[N],ne[N<<1],to[N<<1],js[N],vis[N],sz[N];
int tot,n,rt,mx,ans;
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}

struct com{db r,i;};
com operator * (com a,com b) {return (com){a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r};}
com operator + (com a,com b) {return (com){a.r+b.r,a.i+b.i};}
com operator - (com a,com b) {return (com){a.r-b.r,a.i-b.i};}
com operator / (com a,db b) {return (com){a.r/b,a.i/b};}
com D[262150],kD[262150];int rev[262150];
void FFT(com *a,int n,int x) {
    for(RI i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
    for(RI i=1;i<n;i<<=1) {
        com wn=(com){cos(pi/i),sin(pi/i)*x};
        for(RI j=0;j<n;j+=(i<<1)) {
            com t1,t2,w=(com){1,0};
            for(RI k=0;k<i;++k,w=w*wn)
                t1=a[j+k],t2=w*a[j+i+k],a[j+k]=t1+t2,a[j+i+k]=t1-t2;
        }
    }
    if(x==-1) for(RI i=0;i<n;++i) a[i]=a[i]/n;
}
void orzCai(com *a,int n) {
    int kn=1,len=0;
    while(kn<=n+n) kn<<=1,++len;
    for(RI i=n+1;i<kn;++i) a[i]=(com){0,0};
    for(RI i=1;i<kn;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
    FFT(a,kn,1);
    for(RI i=0;i<kn;++i) a[i]=a[i]*a[i];
    FFT(a,kn,-1);
}

#define mxx(x,y) (x>y?x:y)
void getrt(int x,int las,int SZ) {
    sz[x]=1;int bl=0;
    for(RI i=h[x];i;i=ne[i])
        if(to[i]!=las&&!vis[to[i]])
            getrt(to[i],x,SZ),sz[x]+=sz[to[i]],bl=mxx(bl,sz[to[i]]);
    bl=mxx(bl,SZ-sz[x]);
    if(bl<mx) mx=bl,rt=x;
}
int dlim=0;
void dfs(int x,int las,int d) {
    if(d>dlim) ++dlim,D[dlim]=(com){0,0};
    ++D[d].r;
    for(RI i=h[x];i;i=ne[i])
        if(to[i]!=las&&!vis[to[i]]) dfs(to[i],x,d+1);
}
void work(int x,int SZ) {
    vis[x]=1,++js[1];
    int ddd=0;
    for(RI i=0;i<=SZ;++i) kD[i]=(com){0,0};
    for(RI i=h[x];i;i=ne[i]) {
        if(vis[to[i]]) continue;
        dlim=0,D[dlim]=(com){0,0},dfs(to[i],0,1);
        for(RI j=1;j<=dlim;++j) {
            js[j+1]=qm(js[j+1]+(LL)(D[j].r+0.2)%mod);
            js[j+1]=qm(js[j+1]+(LL)(D[j].r+0.2)%mod);
            kD[j].r+=D[j].r;
        }
        orzCai(D,dlim);
        for(RI j=2;j<=dlim+dlim;++j) js[j+1]=qm(js[j+1]+qm(mod-(LL)(D[j].r+0.2)%mod));
        ddd=mxx(dlim,ddd);
    }
    orzCai(kD,ddd);
    for(RI i=2;i<=ddd+ddd;++i) js[i+1]=qm(js[i+1]+(LL)(kD[i].r+0.2)%mod);
    for(RI i=h[x];i;i=ne[i]) {
        if(vis[to[i]]) continue;
        mx=inf,getrt(to[i],x,sz[to[i]]),work(rt,sz[to[i]]);
    }
}
int main()
{
    int x,y;
    n=read();
    for(RI i=1;i<n;++i) x=read(),y=read(),add(x,y),add(y,x);
    mx=inf,getrt(1,0,n),work(rt,n);
    for(RI i=1;i<=n;++i) ans=qm(ans+1LL*js[i]*ksm(i,mod-2)%mod);
    for(RI i=1;i<=n;++i) ans=1LL*ans*i%mod;
    printf("%d\n",ans);
    return 0;
}