2020-2021:teams:i_dont_know_png:nikkukun:pruefer-sequences
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:nikkukun:pruefer-sequences [2020/08/07 17:28] nikkukun 创建 |
2020-2021:teams:i_dont_know_png:nikkukun:pruefer-sequences [2020/08/07 18:10] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| ===== Prufer 序列的性质 ===== | ===== Prufer 序列的性质 ===== | ||
| + | - $n$ 个节点的无根树的 Prufer 序列长度为 $n-2$。 | ||
| - 在构造完 Prufer 序列后原树中会剩下两个结点，其中一个一定是编号最大的点； | - 在构造完 Prufer 序列后原树中会剩下两个结点，其中一个一定是编号最大的点； | ||
| - | - 每个结点在序列中出现的次数是其度数减 $1$，没有出现的就是叶结点。 | + | - 度为 $d$ 的节点会出现 $d-1$ 次，没有出现的就是叶结点。 |
| - | 我们知道 Prufer 序列可以得到 Cayley 公式，即带标号无根树的个数是 $n^{n-2}$ 的，因为对应的 Prufer 序列就有这么多种。同时由于 Prufer 序列还体现了树中度数的关系，因此也可以用来做一些度数有限制的生成树计数。 | + | 我们知道 Prufer 序列可以得到 Cayley 公式，即带标号无根树的个数是 $n^{n-2}$ 的，因为对应的 Prufer 序列就有这么多种。同时由于 Prufer 序列还体现了树中度数的关系，因此也可以用来做一些度数有限制的生成树计数。例如，设已知节点的度数组 $d_1, d_2, \ldots, d_n$，则其无根树的数量为 |
| - | 带度数限制的例子可以参考 [[http://wiki.buaaacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7#i_-valuable-forests | Valuable Forests]] 这道题的树形 DP 解法。 | + | $$ |
| + | \dfrac {(n-2)!}{\prod_{i=1}^n (d_i - 1)!} | ||
| + | $$ | ||
| + | |||
| + | 证明只要考虑“度为 $d$ 的节点会出现 $d-1$ 次”这个性质即可。另一个带度数限制的例子可以参考 [[http://wiki.buaaacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7#i_-valuable-forests | Valuable Forests]] 这道题的树形 DP 解法。 | ||
| 行 34: | 行 39: | ||
| ===== 参考资料 ===== | ===== 参考资料 ===== | ||
| - | * [[https://oi-wiki.org/graph/prufer/#_4 | Prufer 序列 - OI Wiki]] | + | - [[https://oi-wiki.org/graph/prufer/#_4 | Prufer 序列 - OI Wiki]] |
2020-2021/teams/i_dont_know_png/nikkukun/pruefer-sequences.1596792493.txt.gz · 最后更改: 2020/08/07 17:28 由 nikkukun
