无根树转化为$prufer$序列

每次找到编号最小的叶子节点
删除该节点并在序列中添加与该节点相连的节点的编号
重复$1,2$操作，直到整棵树只剩下两个节点

$prufer$序列转化为无根树

每次取出$prufer$序列中最前面的元素$u$
在点集$V$（$V$初始化为$ { 1,2,…,n } $）中找到编号最小的没有在$prufer$序列中出现的元素$v$
给$u,v$连边然后在序列中删除$u$，在$V$中删除$v$
重复$1,2,3$,直到序列为空。此时在点集$V$中剩下两个节点，给它们连边即可

其中点集$V$用$set$维护可以做到$P(nlogn)$的复杂度

证明

注意到，如果一个节点$A$不是叶子节点，那么它至少有两条边；但在无根树转化为$prufer$序列的过程结束后，整个图只剩下一条边，因此节点$A$的至少一个相邻节点被去掉过，节点A的编号将会在这棵树对应的$prufer$编码中出现。反过来，在$prufer$编码中出现过的数字显然不可能是这棵树（初始时）的叶子。于是我们看到，没有在$prufer$编码中出现过的数字恰好就是这棵树（初始时）的叶子节点。把序列的第一个元素和$V$中最小编号的未出现点删除后，即在原树中删除了一个叶子节点和对应的边，剩下的新树和剩下的$prufer$序列以及$V$仍然满足以上性质（只是多了个必须在$V$中出现的限制，这是因为不在$V$中出现的点此时已经不在新树中了）（如果想不明白对应关系的话，可以考虑画两个图，第一个图即原树（可以看作$V$），第二个图是利用$prufer$序列构造的树，每在原树中删除一个顶点一条边，就在第二个图中加入一条边）

性质

$prufer$序列中节点$i$出现的次数为$d_i-1$
一棵$n$个节点的无根树唯一地对应了一个长度为$n-2$的数列，数列中的每个数都在$1$到$n$的范围内（考虑转换中的$4$步，每一步都一定可行，第$3$步中序列的大小总比$V$大$2$，所以总能找到满足的$v$）
$n$个节点的有标号无根树有$n^{(n-2)}$个，也可以看作完全无向图的生成树个数
$n$个节点的度数分别为$d_1,d_2,…,d_n$的无根树共有$\frac {(n-2)!} {\Pi(d_i-1)!}$个，因为此时$prufer$序列中节点$i$出现了$d_i-1$次（又因为该性质的存在，$prufer$序列常用于$dp$计算有度数限制的有标号无根树计数中）
$n$个节点的有根树有$n^{(n-2)}*n=n^{(n-1)}$
考虑有$n$个节点，$m$棵树的有根树森林计数我们建一个虚点$n+1$，然后构造一棵$n+1$个点的无根树，并假定以$n+1$号点为根，然后把虚点拆掉，它的儿子就会形成若干棵有根树森林，我们只需要保证$n+1$号点的度数恰好为$m$即可。所以方案数为$C_{n-1}^{m-1}\ n^{n-m}$
接下来我们考虑不限制有多少棵树的有根树森林。可以由上面建虚点的方法直接得到方案数$(n+1)^{n-1}$