题目链接：传送门
思路：
计数。树的结构和边权的计数可以分开讨论。
①假设从a到b的路径上有e条边，那么路径上就有e-1个点。构造这条路径上的点有$A_{n-2}^{e-1}$种方案；
②这条路径的权值的选择，可以用隔板法来做，相当于用e-1个隔板分开m个球，要求每个区间至少有一个球，那么就相当于在m-1个间隙里插入e-1个隔板，有$C_{m-1}^{e-1}$种方案；
③在路径之外的点还有n-e-1个，对应有n-e-1条边，每条边的权值可取[1, m]，所以有mn-e-1种方案；
④在路径之外的点构造成树，相当于把剩下的点挂在之前的e+1个点上。这等价于从n个点建一个有e+1棵树，并且有e+1个节点分别在不同的树上，的森林。
根据广义Cayley定理可知，从x个点建一个有y棵树的森林，使得给定的y个节点各自属于不同的树上，的方案数为f(x, y) = y*xx-y-1；
【此处广义Cayley的理解参考了jklover的博客】
因此有f(n, e+1)种方案。
综上所述，a到b的路径上有e条边的方案数为plan(e) = $A_{n-2}^{e-1}*C_{m-1}^{e-1}*m^{n-e-1}*f(n, e+1)$。
实现代码：
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 5;
const int md = 1e9 + 7;
inline int add(int a, int b) {
int res = (a+b)%md;
if (res < 0)
res += md;
return res;
}
inline int mul(int a, int b) {
return (int)(1LL * a * b % md);
}
int fpow(int a, int p) {
int res = 1;
for (; p; p >>= 1) {
if (p & 1)
res = mul(res, a);
a = mul(a, a);
}
return res;
}
inline int f(int x, int y) {
if (x == y)
return 1;
return mul(y, fpow(x, x-y-1));
}
int fac[MAX_N], inv[MAX_N];
void init() {
fac[0] = 1;
for (int i = 1; i < MAX_N; i++)
fac[i] = mul(fac[i-1], i);
inv[MAX_N-1] = fpow(fac[MAX_N-1], md-2);
for (int i = MAX_N-1; i > 0; i--)
inv[i-1] = mul(inv[i], i);
}
inline int A(int m, int n) {
return mul(fac[m], inv[m-n]);
}
inline int C(int m, int n) {
if (n > m)
return 0;
return mul(A(m, n), inv[n]);
}
int main()
{
init();
int n, m, a, b;
cin >> n >> m >> a >> b;
int ans = 0;
for (int e = 1; e <= n-1; e++) {
int tmp = 1;
tmp = mul(tmp, A(n-2, e-1));
tmp = mul(tmp, C(m-1, e-1));
tmp = mul(tmp, fpow(m, n-e-1));
tmp = mul(tmp, f(n, e+1));
ans = add(ans, tmp);
}
cout << ans << endl;
return 0;
}
好久没写博客了呀（计数器劝退），不过碰到好题还是忍不住要回来扯两句QwQ。
Codeforces1113F. Sasha and Interesting Fact from Graph Theory（组合数学 计数 广义Cayley定理）
原文：https://www.cnblogs.com/Lubixiaosi-Zhaocao/p/10453896.html