Link.
Description.
给定一棵树，约定一个序列 \(\{a_i\}\) 是合法的，当且仅当：
- \(\forall i\in[1,n],\exists j\in[1,i),(a_i,a_j)\in\mathbf G\)
一个序列的价值定义为逆序对数，求价值期望。
Solution.
逆序对没有什么优美的性质。
所以我们考虑把期望拆成 \(i\ge j\)，在序列中 \(i\) 排在 \(j\) 前面的概率和。
然后发现第一个点没有什么限制，和后面不同，考虑枚举第一个点。
接下来我们需要判断取到 \(x\) 在取到 \(y\) 前的概率。
首先我们发现直到 \(\text{LCA}(x,y)\)，都不会对概率造成影响。
取其他的元素也不会对这个概率造成影响，因为它是概率。
问题转化成了给两个数，每次有一半的概率给第一个数减一，一半的概率给第二个数减一。
发现问题维度是 \(2\) 维的，直接做一个 \(O(n^2)\) 的 dp 预处理即可。
因为我们枚举了 \(a_1\)，所以还需要乘上 \(\frac 1n\)。
Coding.
点击查看代码
//是啊，你就是那只鬼了，所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}/*}}}*/
const int P=1e9+7,I2=(P+1)>>1;char lcv[205];int dp[205][205];
inline int ksm(int x,int q=P-2) {int r=1;for(;q;q>>=1,x=1ll*x*x%P) if(q&1) r=1ll*r*x%P;return r;}
struct edge{int to,nxt;}e[405];int et,head[205],n,lc[205][205],dep[205];
inline void adde(int x,int y) {e[++et]=(edge){y,head[x]},head[x]=et;}
inline void dfs0(int x,int fa)
{
for(int i=1;i<=n;i++) if(lcv[i]) lc[i][x]=lc[x][i]=lc[fa][i];
lcv[x]=1,lc[x][x]=x,dep[x]=dep[fa]+1;
for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) dfs0(e[i].to,x);
}
int main()
{
read(n);for(int i=1,x,y;i<n;i++) read(x,y),adde(x,y),adde(y,x);
for(int i=0;i<=n;i++) dp[0][i]=1;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=1ll*(dp[i-1][j]+dp[i][j-1])*I2%P;
//for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) printf("%d%c",dp[i][j],j==n?'\n':'\t');
int rs=0;for(int rt=1;rt<=n;rt++)
{
dfs0(rt,0);for(int x=1,l;x<=n;x++) for(int y=1;y<x;y++)
l=lc[x][y],rs=(rs+dp[dep[x]-dep[l]][dep[y]-dep[l]])%P;
}
return printf("%lld\n",1ll*rs*ksm(n)%P),0;
}