prufer序列

prufer序列prufer序列是一种无根树的序列表示方法，一个节点个数为 $n$ 的无根树对应着唯一一种长度为 $n - 2$ 的prufer序列 无根树化prufer序列每次取编号最小的叶子节点，将其指向的“父亲”（就是它唯一指向的）节点加入prufer序列中，最终剩余两个连接的节点结束 prufer序列化无根树对于prufer序列 $A= \{a_1, a_2, a_3, …\}$，每次取最前面的元素 $a_s$，在总点集中找到最小的没有在 $A$ 中的节点 $t$，将 $a_s, t$ 连边并删去 $a_s$，可以使用 $set$ 等维护 相关定理 $n$ 个点的有标号完全图无根树计数：$n^{n - 2}$ $n$ 个点，每个点的度数为 $\{d_1, d_2, d_3, …\}$ 的有标号无根树计数：$\frac{(n - 2)!}{d_1!d_2!d_3!…}$（实际上就是一个多重集的排列数） $n$ 个点的prufer序列中第 $i$ 个点恰好出现 $d_i - 1$ 次 $n$ 个点度数为 $\{d_1, d_2, …, d_k\}$，剩余 $k + 1 \thic ...

对于 $n$ 个点组成的环大小为 $m$ 的基环树个数的问题，目前已知三种解法 解法一「动态规划」在环上每个点下面搭树的方案数，相当于是在完全图中制造生成树，然后提一个点（即环上那个点）为根，故可用 $n^{n - 2}$ 来计算 然后就可以很容易想到一种背包解法，把环随便找个地方断一下，把它看成序列，即可令 $f_{i, j}$ 表示环序列前 $i$ 个点，已经使用了 $j$ 个点做环下的树的方案数，显然$$f_{i, j} = \sum\limits_{k = 0}^j f_{i - 1, j - k} \times \dbinom{n - m - (j - k)}{k} \cdot (k + 1)^{k - 1}$$然后答案要对环进行圆排列，即 $ans = f_{m, n - m} \times \frac{A_n^m}{2m}$ 复杂度 $O (n^3)$ 当然这样复杂度比较高，可以考虑将已经拼好的连通块和已经拼好的一棵树连接起来，令 $f_n$ 表示 $n$ 个点的答案 当然，为了保证不会算重，需要有一个特征点，即保证点 $1$ 不会在环上，即$$f_n = \frac{n ...