Description

题目链接

题目大意：给出 $n$ 个点的树，进行如下操作：

• 首先等概率选取一个点打上标记
• 等概率选取一个未打上标记且有一条边连向打上标记的点打上标记，当所有点都打上标记时退出操作

求按照时间先后形成的序列的期望逆序对数。$1 \le n \le 200$。

Solution

很容易想到对每个点作为根的情况求一遍，然后除以 $n$ 就是答案。

我们考虑逆序对是怎么来的，无非是有一对 $i, j$，满足 $i < j, a_i > a_j$，在这道题里就是 $a_i$ 先被打上标记，$a_j$ 后被打上标记。

我们考虑从根到这两个点的路径，不难发现第一个被打上标记的是这两个点的 LCA，问题可以转化为已知 LCA，求先到 $i$，后到 $j$ 的概率。如果设两点到 LCA 距离为 $x, y$，那么显然有 $f(x, y) = \frac{1}{2} \cdot (f(x - 1, y) + f(x, y - 1))$。

然后就做完了，时间复杂度 $O(n^3 \log n)$。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

const int mod = 1e9 + 7;
const int maxn = 200 + 10;

std::vector<int> g[maxn];
LL f[maxn][maxn];
LL ans;
int top[maxn], dfn[maxn], siz[maxn], dep[maxn], fa[maxn], son[maxn];
int n, cnt;

LL qPow(LL a, int b) {
    LL s = 1;
    while (b) {
        if (b & 1)    s *= a, s %= mod;
        a *= a, a %= mod;
        b >>= 1;
    }
    return s;
}

int inv(int x) { return qPow(1LL * x, mod - 2); }

void dfs1(int x, int p) {
    dep[x] = dep[p] + 1;
    siz[x] = 1;
    fa[x] = p;
    for (auto i : g[x]) {
        if (i != p) {
            dfs1(i, x);
            siz[x] += siz[i];
            if (siz[i] > siz[son[x]])    son[x] = i;
        }
    }
}

void dfs2(int x, int p) {
    top[x] = p;
    dfn[x] = ++cnt;
    if (son[x]) {
        dfs2(son[x], p);
        for (auto i : g[x]) {
            if (i != fa[x] && i != son[x]) {
                dfs2(i, i);
            }
        }
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]])    v = fa[top[v]];
        else    u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

int main() {
    read(n);
    for (int i = 1, u, v; i < n; ++i) {
        read(u), read(v);
        g[u].push_back(v), g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)    f[0][i] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) % mod * 500000004 % mod;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)    son[j] = 0;
        dfs1(i, 0);
        dfs2(i, i);
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k < j; ++k) {
                int w = lca(j, k);
                ans += (f[dep[j] - dep[w]][dep[k] - dep[w]]) % mod;
                ans %= mod;
            }
        }
    }
    printf("%lld\n", ans % mod * inv(n) % mod);
    return 0;
}