CF1109D Sasha and Interesting Fact from Graph Theory

神秘 prufer 序列 + 组合数学。

题意：有多少棵 $n$ 个点的树，满足每一条边的边权在 $[1, m]$ 中，且满足 $a, b$ 的距离为 $m$。$n, m\leq 10 ^ 6$。

直接考虑 prufer 序列计算，首先枚举 $a, b$ 之间一共有多少点，设为 $d$，此时我们需要枚举 $a, b$ 之间的点分别是哪些，贡献为 $(n - 2) ^ \underline{d - 2}$。然后考虑中间的边权，容易得到 $d - 1$ 个的和为 $m$，那么就是 $\binom{m - 1}{d - 1}$。然后考虑剩下的贡献。注意到其实 $d$ 个点可以看作缩成了一个点，还剩 $n - d + 1$ 个点，只不过每次他的出现，可以有 $d$ 个可连。

和度数相关，考虑 prufer 序列。先不管复杂度，考虑枚举 prufer 序列，枚举缩的大点在 prufer 序列中出现了 $j$ 次，那么贡献需要选 $j$ 个位置，为 $\binom{n - d - 1}{j}$，然后每个 $d$ 个点都可以连，为 $d ^ {j + 1}$（注意是出现次数 +1 为度数），剩下的点随便选，为 $(n - d)$ 种，总贡献为 $(n - d) ^ {n - d - j - 1}$。还有边权没有算，容易得到就是 $m ^ {n - d}$。

于是总贡献可以写作：

$$\sum_{d = 2} ^ n (n - 2) ^ \underline{d - 2} \binom{m - 1}{d - 1}m ^ {n - d} \sum_{j = 0} ^ {n - d - 1} \binom{n - d - 1}j d ^ {j + 1} (n - d) ^ {n - d - j - 1}$$

注意到后面的 $d ^ {j + 1}$ 去掉一个 $d$ 移到前面，后面就是一个二项式定理。可以写作：

$$\sum_{d = 2} ^ n (n - 2) ^ \underline{d - 2} \binom{m - 1}{d - 1} m ^ {n - d} n ^ {n - d - 1}$$

但是注意 $d = n$ 时会出锅，于是对 $d = n$，单独计算，为 $(n - 2)!\binom{m - 1}{n - 2}$。直接计算即可，时间复杂度 $O(n\log n)$ 或 $O(n)$。

int main()
{
	init();
	int n, m;
	scanf("%d %d %*d %*d", &n, &m);
	int res = (LL) C(m - 1, n - 2) * fact[n - 2] % Mod;
	for (int i = 2; i < n; ++ i)
		res = (res + (LL) qpow(m, n - i) * C(m - 1, i - 2) % Mod * fact[n - 2] % Mod
			* infact[n - i] % Mod * i % Mod * qpow(n, n - i - 1)) % Mod;
	std::cout << res << std::endl;
	return 0;
}