题目链接：Codeforces 1113F

在本题中，树是一个加权连通图，由 $n$ 个节点和 $n-1$ 条边组成，边的权值为 $1$ 到 $m$ 的整数。一棵树是美丽的，当且仅当对于给定的节点 $a$ 和 $b$，他们的距离恰好为 $m$。

请你求出有多少棵树是美丽的，答案对 $10^9+7$ 取模。两棵树是不同的，当且仅当一棵树上有一条边，而另一棵树上没有这条边。

数据范围：$2\le n\le 10^6$，$1\le m\le 10^6$，$1\le a,b\le n$，$a\neq b$。

Solution

首先我们发现 $a$ 和 $b$ 的值是没有用的，只不过是钦定了两个点罢了（答案不能乘以 $\binom{n}{2}$ 而已）。

我们枚举 $a$ 和 $b$ 之间的边数 $i$，那么这条路径上有 $i-1$ 个点，有 $A(n-2,i-1)$ 种选法。这 $i$ 条边的权值和为 $m$ 则有 $\binom{m-1}{i-1}$ 种边权的分配方法（考虑隔板法）。对于不在路径上的边，它的边权是任意的，那么有 $m^{n-1-i}$ 种方案。

最后是最难计算的部分：将 $n$ 个点组成一个有 $i+1$ 个根节点的森林。考虑 Cayley's formula：$T(n,k)$ 表示将 $n$ 个有标号点组成一个 $k$ 个连通块的森林的方案数，有 $T(n,k)=k\cdot n^{n-k-1}$。

故最终答案为：

$$ \sum_{i=1}^{n-1} A(n-2,i-1)\times \binom{m-1}{i-1}\times m^{n-i-1}\times T(n,i+1) $$

注意在 $A,C,T$ 函数中判断特殊情况的方案数！

时间复杂度：$\mathcal O(n+m)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e6 + 5;
const int mod = 1e9 + 7;

int n, m, fac[N], inf[N], pwn[N], pwm[N];

void add(int &x, int y) {
    (x += y) >= mod && (x -= mod);
}
int pow(int x, int p) {
    int ans = 1;
    for (; p; p >>= 1, x = 1LL * x * x % mod) {
        if (p & 1) ans = 1LL * ans * x % mod;
    }
    return ans;
}
void init(int mx) {
    fac[0] = pwn[0] = pwm[0] = 1;
    for (int i = 1; i <= mx; i++) {
        fac[i] = 1LL * fac[i - 1] * i % mod;
        pwn[i] = 1LL * pwn[i - 1] * n % mod;
        pwm[i] = 1LL * pwm[i - 1] * m % mod;
    }
    inf[mx] = pow(fac[mx], mod - 2);
    for (int i = mx; i >= 1; i--) {
        inf[i - 1] = 1LL * inf[i] * i % mod;
    }
}
int A(int n, int m) {
    if (n < m) return 0;
    return 1LL * fac[n] * inf[n - m] % mod;
}
int C(int n, int m) {
    if (n < m) return 0;
    return 1LL * fac[n] * inf[m] % mod * inf[n - m] % mod;
}
int F(int n, int k) {
    if(n <= k) return 1;
    return 1LL * k * pwn[n - k - 1] % mod;
}
int main() {
    scanf("%d%d", &n, &m);
    init(std::max(n, m));
    int ans = 0;
    for (int i = 1; i < n; i++) {
        add(ans, 1LL * A(n - 2, i - 1) % mod * C(m - 1, i - 1) % mod * F(n, i + 1) % mod * pwm[n - i -1] % mod);
    }
    printf("%d\n", ans);
}