分析

逆序对是由两个元素构成的，所以对于逆序对的期望个数，可以看作是每一个数对能够成为逆序对的期望的和。

直接做很不可做，而每个逆序对只与两个数有关，一般这时候就要考虑计算贡献了。

由于是在树上操作，而所有操作都要跟在第一次标记后面，且根是不固定的，所以可以枚举每一个点作为根的情况，求出所有情况的和之后再乘 \(\frac{1}{n}\) 就好了。

考虑 \((i,j)\)，其中 \(i < j\)，什么时候能够成为逆序对。显然，当且仅当 \(i\) 在 \(j\) 之后被标记，这个期望是多少呢？由于规定了根，而后续的操作必然是不断由根向下标记，也就是说，当 \(lca(i,j)\) 没有被标记的时候，两点被标记的概率都为 \(0\)。而当 \(lca(i,j)\) 被标记后，才能不断向两点所在位置扩充。

要在 \(lca(i,j)\) 被标记之后这个局面求 \(i\) 在 \(j\) 之后被标记的概率（权值是 \(1\)），才能算出对答案有贡献的期望。而其他局面的概率全部为 \(0\)，进而期望全部为 \(0\)。考虑到每次的根是不固定的，但是对于到 \(lca\) 距离相同的点对，产生逆序对的概率则是一样的，所以要如下设计状态。

设 \(f(i,j)\) 为在某对点的 \(lca\) 被标记后，到 \(lca\) 距离为 \(i\) 的点在到 \(lca\) 距离为 \(j\) 的点之前被标记，所能贡献的期望逆序对个数。 \[ f(i,j) = 1 \cdot \frac{f(i-1,j)+f(i,j-1)}{2} \] 当然这个 \(1\) 也可以省略，那么某种意义上说 \(f(i,j)\) 表示的也是概率……

可以 \(O(n^2)\) 预处理。

当以 \(i\) 为根时，预处理查找 \(lca\) 的倍增数组，然后 \(O(n^2)\) 枚举点对，累加期望即可。

最后乘 \(\frac{1}{n}\)。

复杂度 \(O(n^3 \log_2 n)\)，官方题解说可以做到 \(O(n^3)\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=205;
const ll mod=1e9+7, inv2=(1e9+8)/2;
int n, dep[N], fa[N][10];
int tot, h[N], to[N<<1], nxt[N<<1];
ll ans, f[N][N];
void add(int x,int y) {
    to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
ll fp(ll x,ll y) {
    ll ans=1;
    for(;y;x=x*x%mod,y>>=1ll) if(y&1ll) ans=ans*x%mod;
    return ans;
}
void dfs(int x,int fr) {
    fa[x][0]=fr, dep[x]=dep[fr]+1;
    for(int i=1;i<=8;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fr) continue;
        dfs(y,x);
    }
}
int lca(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=8;~i;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=8;~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
    return fa[x][0];
}
signed main() {
    scanf("%d",&n);
    for(int i=1;i<n;++i) {
        int x, y; scanf("%d%d",&x,&y);
        add(x,y), add(y,x);
    }
    for(int i=1;i<=n;++i) f[0][i]=1ll;
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
        f[i][j]=(f[i-1][j]+f[i][j-1])*inv2%mod;
    for(int i=1;i<=n;++i) {
        dfs(i,0);
        for(int j=1;j<=n;++j) for(int k=1;k<j;++k) {
            int l=lca(j,k);
            (ans+=f[dep[j]-dep[l]][dep[k]-dep[l]])%=mod;
        }
    }
    printf("%lld\n",ans*fp(n,mod-2)%mod);
}