Codeforces Round #728 (Div. 2)

题意：

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

解析：

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

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

对于上述情况，可以将其上述概率，抽象为两个栈，其中分别有从lca(a,b)lca(a,b)到aa和bb路径上的节点。每次随机从两个栈中取出一个节点，直到b栈先被取空的概率。设栈aa大小为xx，栈bb大小为yy，则概率为dp[x][y]dp[x][y]。考虑转移，等同于每次从[x−1][y][x-1][y]或[x][y−1][x][y-1]的状态随机放入的概率，故dp[x][y]=dp[x][y−1]+dp[x−1][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;
}