Codeforces Round #728 (Div. 2)

题意:

给定一棵有nn个节点的树,第一次可以在树上等概率选择一个节点,之后每次在与已选择节点相连的未选择节点里等概率选择一个节点,直到全部选完。问按选择顺序排序的数组中,逆序对数量的期望。

解析:

这个问题可以看做为固定一个节点,并从固定的节点开始逐渐拓展节点的过程。固定节点之后,我们可以求以当前固定节点为根的一种期望。

考虑一对节点(a,b)(a,b),其中a<ba<b,那么这对节点对答案有贡献当且仅当bbaa之前被遍历到。由于树当中根节点到达一个点仅有一条路径,且在到达lca(a,b)lca(a,b)节点前的概率,和选择不在路径上的节点的概率,对bbaa谁先选择到的概率无影响,故仅需考虑lca(a,b)lca(a,b)分别到aabb的情况即可。

对于上述情况,可以将其上述概率,抽象为两个栈,其中分别有从lca(a,b)lca(a,b)aabb路径上的节点。每次随机从两个栈中取出一个节点,直到b栈先被取空的概率。设栈aa大小为xx,栈bb大小为yy,则概率为dp[x][y]dp[x][y]。考虑转移,等同于每次从[x1][y][x-1][y][x][y1][x][y-1]的状态随机放入的概率,故dp[x][y]=dp[x][y1]+dp[x1][y]2dp[x][y]=\frac{dp[x][y-1]+dp[x-1][y]}{2}。最后对于每个根,遍历ab,求出lca即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>

using namespace std;
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
const int N = 2e2 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
long long dp[N][N];
int father[N][30];
int lg;
struct node{
int v, next;
}a[M];
int f[N], cnt;
void add(int u, int v){
a[++cnt].v = v, a[cnt].next = f[u], f[u] = cnt;
}
int dep[N];
void dfs(int u, int fa, int deep) {
dep[u] = deep;
for (int i = f[u]; i; i = a[i].next) {
int v = a[i].v;
if(v == fa) continue;
father[v][0] = u;
for (int j = 1; j <= lg; j++) father[v][j] = father[father[v][j - 1]][j - 1];
dfs(v, u, deep + 1);
}
}
int inv2;
long long fastpow(long long a, long long k) {
long long res = 1;
while(k) {
if(k & 1) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for (int i = lg; i >= 0; i--) {
if(dep[father[u][i]] >= dep[v])
u = father[u][i];
}
if(u == v) return u;
for (int i = lg; i >= 0; i--) {
if(father[u][i] != father[v][i]){
u = father[u][i];
v = father[v][i];
}
}
return father[u][0];
}
int main(){
inv2 = fastpow(2, mod - 2);
int n;
cin >> n;
int invn = fastpow(n, mod - 2);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
for (int i = 1; i <= n; i++) {
dp[i][0] = 1;
}
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]) % mod * inv2 % mod;
}
lg = (int)log(n) / log(2);
long long ans = 0;
for (int i = 1; i <= n; i++) {
memset(father, 0, sizeof father);
dfs(i, 0, 1);
for (int a = 1; a <= n; a++) {
for (int b = a + 1; b <= n; b++) {
int l = lca(a, b);
ans = (ans + dp[dep[a] - dep[l]][dep[b] - dep[l]] * invn % mod) % mod;
}
}
}
cout << ans << '\n';
return 0;
}