题目链接：Codeforces1109D
题意
求满足以下条件的带标号树的个数：
边权在\([1,m]\cap Z\)
点\(a\)到点\(b\)间的边权和为\(m\)
数据范围：\(n,m≤1e6\)
题解
枚举\(a\),\(b\)间点数为\(i\),可以知道方案数为：
\[ \dbinom{n - 2}{i}\dbinom{m-1}{i}i!m^{n-2-i} f(i) \]
\(\dbinom{n-2}{i}i!\) 是在剩下\(n-2\)个点中选\(i\)个排在\(a\),\(b\)之间。
\(\dbinom{m-1}{i}\) 是\(i+1\)条边和为\(m\)的方案数。
\(m^{n-2-i}\) 是不在\(a\),\(b\)之间的点可以自由选择权值。
\(f(i)\) 是有一个长为\(i+2\)的链（以\(a\),\(b\)为端点）和\(n-i-2\)个独立的点的生成树个数。
事实上，要计算\(f(i)\)，我们可以用一个更强的结论：
已知有\(n\)个点和\(k\)个联通的点集，第\(i\)个点集大小为\(size[i]\)，那么它生成树的个数为：
\[ (\Pi_{i=1} ^ {k} size[i])n^{k-2} \]
设\(P\)是长度为\(k-2\)的\(prufer\)序列的集合，\(P\)中的每个元素和一个\(k\)个点的生成树一一对应。
但和一般的\(k\)个点生成树不同。这里第\(i\)个点的度数\(+1\)，会使答案乘上\(size[i]\)。
设第\(i\)个点集出现在\(prufer\)序列中的次数为\(c_i\)，那么我们要求的答案就是：
\[ \sum_{p\in P} \Pi_{i=1}^{k} size[i]^{c_i+1}\]
把那个\(+1\)提到外面去，就是考虑计算
\[ \sum_{p\in P} \Pi_{i=1}^{k} size[i]^{c_i} \]
因为\(\sum c_i = k-2\) ， 这就相当于走\(k-2\)步，如果走第\(i\)条就产生\(size[i]\)的贡献，求所有方案下的贡献和。
这个就是\((\sum size[i]) ^ {k-2} = n ^ {k - 2}\)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int n, m, a, b;
int fac[N], fav[N], inv[N];
int Qpow(int x, int p) {
if (p == -1) return inv[x];
int ans = 1;
while (p) {
if (p & 1) ans = 1LL * ans * x % mod;
x = 1LL * x * x % mod;
p >>= 1;
}
return ans;
}
int C(int x, int y) {
if (x < y || y < 0) return 0;
return 1LL * fac[x] * fav[y] % mod * fav[x - y] % mod;
}
void upd(int &x, int y) {
(x += y) >= mod ? x -= mod : 0;
}
int main() {
cin >> n >> m >> a >> b;
int ans = 0;
fac[0] = fav[0] = 1;
for (int i = 1; i < N; ++i) {
inv[i] = Qpow(i, mod - 2);
fac[i] = 1LL * fac[i - 1] * i % mod;
fav[i] = 1LL * fav[i - 1] * inv[i] % mod;
}
for (int i = 0; i <= n - 2; ++i) {
int tmp = 1LL * C(n - 2, i) * C(m - 1, i) % mod;
tmp = 1LL * tmp * fac[i] % mod;
tmp = 1LL * tmp * Qpow(m, n - 2 - i) % mod;
tmp = 1LL * tmp * (i + 2) % mod;
tmp = 1LL * tmp * Qpow(n, n - i - 3) % mod;
upd(ans, tmp);
}
cout << ans << endl;
return 0;
}