Prufer编码的一些东西

发表于 | 更新于

prufer 基本上是转的->Dapper除了格式之外，写的不错

无约束条件

如果每个点的度数没有限制，那么一共有nn个点，每个点可以出现在 数列中的任意位置， ，不同的prufer必定对应不同的树，由于 数列长度为n−2n-2，那么不同的构成的树共有nn−2n^{n-2}种。

所有点的度数有限制

如果点的度数有限制，则一个度数为xx的节点在 数列中只会出现x−1x-1次 如果这个节点是叶节点，即x==1x==1，显然成立 否则，若度数为xx，那么它被删边x−1x-1次，即加入数列x−1x-1次后成为叶节点，然后它就不会被再加入数列了 综上所述，结论成立

则设did_i表示第ii个节点的度数，只要求出 序列的总数就行了 Ans=Cn−2d1−1Cn−2−(d1−1)d2−1...Cdn−1dn−1Ans=C_{n-2}^{d_1-1}C_{n-2-(d_1-1)}^{d_2-1}...C_{d_n-1}^{d_n-1} =(n−2)!∏(di−1)!=\dfrac {(n-2)!}{\prod(d_i-1)!}

混合的情况

BZOJ 1005 明明的烦恼 就是分别求出没有度数限制和有度数限制的情况，相乘即可，注意高精度运算。