prufer-526互联

1. prufer序列中某个编号出现的次数就等于这个编号的节点在无根树中的度数$(d)-1$
2. 一棵$n$个节点的无根树唯一地对应了一个长度为$n-2$的数列，数列中的每个数都在$1$到$n$的范围内。
3. n个点的无向完全图的生成树的计数: $n^{n-2}$ ，即n个点的有标号无根树的计数
4. $n$个节点的度依次为$d_1,d_2,…,d_n$的无根树共有$\frac{(n-2)!}{\prod^n_{i=1}(d_i-1)!}$个，因为此时Prufer编码中的数字$i$恰好出现$d_i-1$次,$(n-2)!$是总排列数
5. $n$个点的有标号有根树的计数：$n^{n-2}\cdot n=n^{n-1}$
6. 一个 $n$ 个点 $m$ 条边的带标号无向图有 $k$ 个连通块。我们希望添加 $k-1$ 条边使得整个图连通的方案数为$n^{k-2}\cdot\prod_{i=1}^ks_i$($s_i$为连通块大小)（带权Cayley）->CF156D。
7. 构造：删编号最小叶节点（双射）
8. prufer序列中的出现次数代表儿子个数。