题目链接：

Tree Array

题目大意：

给你一棵n个结点的数，你可以生成一个序列。

开始时，你随机地标记一个结点。任意时刻，那些没有标记但能通过一条边连接标记了的点的点构成一个集合，你从这个集合中等概率地标记一个点。重复操作，直到标记完所有点。

标记点的顺序就是这个序列，求这个序列逆序对数的期望。

1 ≤ n ≤ 200

感想：

这道题融合了期望，逆元，数，dp，是一道非常棒的题目。

解法总是可望不可及。做题时绞尽脑汁，依然不会做。看到解法后，回过头来，发现自己总是只差一点。也许这最后一步是我最难克服的问题。也许是我基础知识不扎实的缘故吧。

我可以总结一些经验，就是集合操作我还不能把握，如果思考集合操作的话直接放弃，转换其他思路；和的期望等于期望的和，这在期望题中非常重要，在这道题中的应用就是将各种情况下的各点对的期望之和，转换成了各点对在各种情况下的期望之和（确实，情况数接近2ⁿ，而点对数只有n²，这个转化是很合理的）。

题解

我们发现初始时选择不同结点，对逆序对数的影响很大。

我们固定选择点r作为第一个点，也把它作为树的根。那么与他有关的逆序对数已经确定。我们思考其它点对形成的逆序对数。

我们发现两个点u和v对逆序对数做出的贡献至于u到v的路径有关。设l为u和v的最近公共祖先，a为u到l的距离，b为v到l的距离，f(a,b)为u,v产生的逆序对数的期望（v>u）。那么f(a,0)=0, f(0,b)=1, f(a,b)=(f(a-1,b),f(a,b-1))/2。由于n较小，可以预处理出f[200][200]。

那么，我们只需要枚举根结点数，算出每两个点之间的lca，算出每个点的dep即可，然后带入f计算即可。时间复杂度O(N³)

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=210;
const LL M=1e9+7;
//求出1~n的逆元  
LL inv[N];
void line_inv(LL n, LL p){
	inv[1]=1;
	for(int i=2; i<=n; ++i) inv[i]=(p-p/i)*inv[p%i]%p;
}

int n;
vector<int> V[N];
int dep[N], lca[N][N], fa[N];
LL f[N][N];
//求出每个点的深度dep，dfs 
void get_dep(int u, int faa){
	fa[u]=faa;
	for(int i=V[u].size()-1; ~i; --i){
		int v=V[u][i];
		if(v==faa) continue;
		dep[v]=dep[u]+1;
		get_dep(v,u);
	}
}
//求出u和v的lca，记忆化搜索  
int get_lca(int u, int v){
	if(u==v) return lca[u][v]=u;
	if(lca[u][v]) return lca[u][v];
	if(dep[u]>dep[v]) swap(u,v);
	if(dep[v]==dep[u]) return lca[u][v]=lca[v][u]=get_lca(fa[u],fa[v]);
	else return lca[u][v]=lca[v][u]=get_lca(u,fa[v]);
}
//求f[p][q]，记忆化搜索 
int get_f(int p, int q){
	if(f[p][q] || !p || !q) return f[p][q];
	return f[p][q]=(f[p-1][q]+f[p][q-1])*inv[2]%M;
}

int main(){
	//预处理出逆元，f 
	line_inv(N,M);
	for(int i=1; i<N; ++i){
		f[i][0]=1;
		f[0][i]=0;
	}
	for(int i=1; i<N; ++i){
		for(int j=1; j<N; ++j){
			f[i][j]=get_f(i,j);
		}
	}
	cin>>n;
	for(int i=1, u, v; i<n; ++i){
		scanf("%d%d", &u, &v);
		V[u].push_back(v);
		V[v].push_back(u);
	}
	LL ans=0;
	for(int i=1; i<=n; ++i){
		int rt=i;
		for(int u=1; u<=n; ++u){
			for(int v=1; v<=n; ++v){
				lca[u][v]=0;
			}
			fa[u]=0;
		}
		dep[rt]=0; get_dep(rt,rt);
		for(int u=1; u<=n; ++u){
			for(int v=u+1; v<=n; ++v){
				int l=get_lca(u,v);
				int p=dep[u]-dep[l], q=dep[v]-dep[l];
				ans=(ans+f[p][q]*inv[n])%M;
			}
		}
	}
	cout<<ans<<endl;
}

/*
4
1 2
1 3
1 4

4
1 2
3 1
4 2

5
1 2
1 3
1 4
2 5

*/