题解：P15578 [USACO26FEB] Random Tree Generation G

分析

构造方法是：

1. 对于每个点，随机选择一个比其标号小的点作为父亲，生成一棵递增标号树。
2. 对上述树的标号打乱。

不难想到，第一步产生的数则种类有 $\prod_{i=2}^{N} (i-1)$ 个，第二步的排列数有 $N!$ 个可能。所以，总方案数为：

$$\prod_{i=2}^{N} (i-1) \times N!$$

关键点来了：有多少种情况可以生成这个树。反向考虑这棵树能怎么生成，也就是存在一种情况得到了一个递增树和一个排列，可以得到这个树。显然，如果一个递增树可以加上某个排列形成这棵树，那么这个排列是唯一确定的。那么，任意一个与输入的树结构相同的递增标号树都可以得到这个树，做一个贡献。如何计算这个贡献？首先，由定义可知 1 号节点一定是根，令其 $k$ 个子节点的子树大小分别为 $s_1, s_2, \dots, s_k$，则每个子树分配点集方案树为

$$C_{n-1}^{s_1} \times C_{n-1-s_1}^{s_2} \times \dots \times C_{n-1-\sum_{i=1}^{k-1} s_i}^{s_k}$$

化简可得

$$\frac{N!}{s_1! \times s_2! \times \dots \times s_k!}$$

每个子树同样满足这个标号规则，令 $f(T)$ 为以 $T$ 为根的子树的方案，则：

$$f(T) = \frac{N!}{\prod s_i!} \times \prod f(子树i)$$

展开，化简可得：

$$f(T) = \frac{N!}{\prod sz_u}$$

其中，$sz_u$ 表示树上每个节点的子树大小。这样子我们可以求出来一个节点为根的方案树，接下来我们需要换根。

令 $f_u = \frac{N!}{\prod sz_x},\quad f_v = \frac{N!}{\prod sz’_x}$，从 $u$ 到 $v$ 只会有以下树改变：

$$sz_u = N,\quad sz_v = sz_v$$

$$sz_u’ = N-sz_v,\quad sz_v’=N$$
分母产生的变化

$$D_u=(\prod_{x \ne u,v} sz_x) \times N \times sz_v$$

$$D_v = (\prod_{x\ne u,v} sz_x) \times (N-sz_v) \times N$$

比一下，

$$\frac{f_v}{f_u} = \frac{D_u}{D_v} = \frac{N \times sz_v}{(N-sz_v) \times N} = \frac{sz_v}{(N-sz_v)}$$

所以，$f_v = f_u \times \frac{sz_v}{(N-sz_v)}$。

之后我们将其求和，得到总答案数，再逆元除以总情况数即可。

参考代码

#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
int hd[N], nxt[N * 2], to[N * 2], num = 1;
void add(int u, int v) {
    num++;
    to[num] = v;
    nxt[num] = hd[u];
    hd[u] = num;
}
int sz[N];
void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
long long fpow(long long x, long long y) {
    long long res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
int n;
long long f[N];
void dfs2(int u, int fa) {
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        f[v] = f[u] * sz[v] % mod * fpow(n - sz[v], mod - 2) % mod;
        dfs2(v, u);
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        num = 1;
        memset(hd, 0, sizeof(hd));
        for (int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        dfs(1, 0);
        long long fz = 1;  // 分子
        for (int i = 1; i <= n; i++) {
            fz = fz * i % mod;
        }
        long long fm = 1;  // 分母
        for (int i = 1; i <= n; i++) {
            fm = fm * sz[i] % mod;
        }
        f[1] = fz * fpow(fm, mod - 2) % mod;
        dfs2(1, 0);
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += f[i];
            ans %= mod;
        }
        fm = 1;
        for (int i = 1; i <= n - 1; i++) fm = fm * i % mod;
        for (int i = 1; i <= n; i++) fm = fm * i % mod;
        cout << ans * fpow(fm, mod - 2) % mod << endl;
    }
    return 0;
}