题目链接

非常有意思的一道思维题，解法真的让人眼前一亮。

首先，很自然的想法，我们可以枚举根节点，将所有期望求和后除以 $n$ 便可得到答案。

指定完根节点后再来分析题目，题目要求的是逆序对数，我们可以考虑每一对 $(a,b)$ 对答案的贡献。假设 $a > b$，那么我们要求的便是 $a$ 比 $b$ 先取到的概率。因为在取到 $a$ 或 $b$ 前都必须先取到的 $a$ 与 $b$ 的 $LCA$ ，所以我们并不用考虑取到 $LCA$ 前的操作，只需要考虑从 $LCA$ 到 $a$ 和 $b$ 这一段即可。

我们设从 $LCA$ 向 $a$ 或 $b$ 走一步的概率为 $p$ ，那么我们有 $1-2p$ 的概率不做任何操作。但显然的是， $p$的值在每次操作后都会发生变化，并且我们并没有办法去维护它。不过在这题里，我们并不需要去知道走每一步时 $p$ 的具体值，我们只需要保证从 $LCA$ 向 $a$ 与 $b$ 走的概率相同，便可以通过dp计算出先到 $a$ 的概率。具体的，我们设从 $LCA$ 走到 $a$ 要经过 $i$ 步，走到 $b$ 要经过 $j$ 步，那么有 $f_{i,j}=(f_{i-1,j}+f_{i,j-1})/2$. 这也是本题的巧妙之处，树的具体形态不会影响答案，每个数对的贡献只与两个数到他们 $LCA$ 的距离有关

在预处理完 $LCA$ 与 $f$ 数组后，整个算法的时间复杂度为 $O(n^3)$ ，可以通过本题。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL P=1e9+7;
struct Tree{
    int t,nex;
} e[410]; int head[210],tot;
void add(int u,int v) {
    e[++tot].t=v; e[tot].nex=head[u]; head[u]=tot;
}
int n,root;
int fa[210][20],dep[210],lg[210];
void dfs(int x,int fath) {
    dep[x]=dep[fath]+1;
    fa[x][0]=fath;
    for(int i=1;i<=10;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].t;
        if(y == fath) continue;
        dfs(y,x);
    }
    return;
}
int lca(int x,int y) {
    if(dep[x] < dep[y]) swap(x,y);
    while(dep[x] > dep[y]) x=fa[x][lg[dep[x]-dep[y]]];
    if(x == y) return x;
    for(int i=lg[dep[x]];i>=0;i--) {
        if(fa[x][i] == fa[y][i]) continue;
        x=fa[x][i]; y=fa[y][i];
    }
    return fa[x][0];
}
LL qpow(LL x,LL k) {
    LL sum=1;
    while(k) {
        if(k & 1) sum*=x;
        x*=x;
        x%=P; sum%=P;
        k>>=1;
    }
    return sum;
}
LL ans,dp[210][210];
void solve() {
    memset(fa,0,sizeof(fa));
    memset(dep,0,sizeof(dep));
    dfs(root,0);

    for(int i=1;i<=n;i++) {
        for(int j=1;j<i;j++) {
            int fath=lca(i,j);
            int x=dep[i]-dep[fath],y=dep[j]-dep[fath];
            ans+=dp[x][y];
            ans%=P;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1,x,y;i<n;i++) {
        cin>>x>>y;
        add(x,y); add(y,x);
    }
    for(int i=1;i<=n;i++) lg[i]=log(i)/log(2);
    for(int i=0;i<=n;i++) dp[0][i]=1,dp[i][0]=0;
    for(int i=1;i<=n;i++) 
    for(int j=1;j<=n;j++) dp[i][j]=(dp[i-1][j]+dp[i][j-1])*qpow(2,P-2)%P;
    for(int i=1;i<=n;i++) {
        root=i;
        solve();
    }
    cout<<ans*qpow(1ll*n,P-2)%P<<"\n";
    return 0;
}