problem
你尤其钟情 \(a,b\) 这两个数。
对于一棵 N 个节点的树，已知所有边的长度都在 \([1, m]\) 之间，如果节点 \(a\) 和 \(b\) 的距离恰好为 \(m\)，那么你认为这棵树很好看。
问有多少种不同结构的 N 个节点的树。这里不同的定义是，点带标号时边的存在性不同或者边权不同。一百万。
prufer 序列
先辈告诉我们，一个 \(n\) 个点有标号无根树与一个长为 \(n-2\) 的每个数都在 \([1,n]\) 中的序列形成双射（经典错误：是序列不是排列）。
根据先辈告诉我们的定义，我们可以有这些结论：
- \(n\) 个点有标号无根树有 \(n^{n-2}\) 种。
- 对于一个点，它的度数减一就是它在 prufer 序列中的出现次数。因为 \(2(n-1)-n=n-2\)。
solution
首先我们把 \(a\to b\) 这条链拉出来，枚举这条链上有 \(L\) 条边，那么有 \(L-1\) 个不是 \(a,b\) 的点，那么这部分的贡献：
- 选出这 \(L-1\) 个点：\(\binom{n-2}{L-1}(L-1)!\)。注意，它有顺序。
- 给 \(L\) 条边赋权：\(\binom{m-1}{L-1}\)。
然后这条链就可以扔掉了，缩成一个点。这时候一共有 \(k=n-L>0\) 个点。
- 给剩下的 \(k-1\) 条边赋权：\(m^{k-1}\)。
因为我们这个缩链操作非常奇怪所以对应的处理方式更加奇怪：枚举链的度数 \(d<k\)。
- 这 \(d\) 条边每条边都可以随意连向链上的每一个点，\((L+1)^d\)。
观察缩链树的 prufer 序列，其长度为 \(k-2\)，有 \(d-1\) 个位置需要强制设为链点，剩下强制不是，就是说：
- 这个 prufer 序列的方案数为 \(\binom{k-2}{d-1}\boxed{(k-1)}^{(k-2)-(d-1)}\)。
现在我们品尝一下这个式子：请关爱每一个上下界
\[ans=\sum_{1\leq L<n}\binom{n-2}{L-1}\binom{m-1}{L-1}m^{k-1}\boxed{\sum_{1\leq d<k}(L+1)^d\binom{k-2}{d-1}(k-1)^{(k-2)-(d-1)}}. \]可以看到当 \(k=1\) 时后面框住的那一部分是 \(1\)（\(\binom{-1}{-1}=1\)），这给予了我们极大的信心。
下面开始化简框着的部分：请相信，所有数学公式都有最简单的样子
\[\begin{aligned} \boxed{\bf boxed}&=\sum_{1\leq d<k}(L+1)^d\binom{k-2}{d-1}(k-1)^{(k-2)-(d-1)}\\ &=\sum_{1\leq d<k}\binom{k-2}{d-1}(L+1)^d (k-1)^{k-d-1}\\ &=\sum_{0\leq d\leq k-2}\binom{k-2}{d}(L+1)^{d+1} (k-1)^{k-d-2}\\ &=(L+1)\sum_{0\leq d\leq k-2}\binom{k-2}{d} (L+1)^d (k-1)^{k-d-2}\\ &=(L+1)(L+k)^{k-2}=(L+1)n^{k-2} \end{aligned}\]这里是要凑出二项式定理，为此我们不仅换了一次元还提了一个 \((L+1)\)。
特判 \(L=n-1\) 的情况之后，答案：
\[\binom{m-1}{n-2}(n-2)!+\sum_{1\leq L<\leq n-2}\binom{n-2}{L-1}(L-1)!\binom{m-1}{L-1}m^{k-1}(L+1)n^{k-2}. \]广义 Cayley 定理
由此我们引出了广义 Cayley 定理：对于 \(n\) 个有标号的点，将它们划分成 \(k\) 个森林，使得其中 \(k\) 个关键点中没有两个在同一棵树上，的方案数是 \(kn^{n-k-1}\)。
我们已经证明过了，将这 \(k\) 个关键点连成一条链，然后照搬上面的就行了。
标签：标号,Theory,题解,序列,Graph,条边,binom,prufer,个点 From： https://www.cnblogs.com/caijianhong/p/solution-CF1109D.html