有标号无根树和 prufer 序列形成双射的关系。所以有一些性质。
其构造方式是拿一棵树出来，它有许多叶子。找出这些叶子中编号最小id，记录下它的父亲，丢掉。重复这一过程，会得到一个长度为 \(m-2\) 的序列，即 prufer 序列。用堆可以做到单 log，当然也有线性做法（如果它丧心病狂想卡的话），懒得记。
但是这玩意更多是用在无根树的计数方面。它具有很好的性质：每个元素都是可以取到 \([1,m]\) 中的任意数，独立的，即无根树的数量是 \(m^{m-2}\)。还有一个性质是一个点在树中的度等于序列中出现次数加一。主要是这两个性质，有几个比较基础的应用：
P4430 无脑板子。树的形态有 \(m^{m-2}\) 种，边的顺序有 \((m-1)!\) 种，乘起来即可。
P2290 板子。根据性质可以确定每个点在 prufer 序列中的出现次数，简单组合即可。然后有一些需要注意的边角情况但不重要。
P4981 板子，直接输出 \(m^{m-2}\) 即可。
提一嘴线段树优化建边，就不单独开一个随笔了。
除了板子似乎没有其它什么题了，其实更多的是一种思想。板子题link，线段树优化建图是拆边的一种方法，当一个点需要向一个区间内所有节点连边时，我们需要做的就是先把这些节点按照建线段树的方式来分组，然后对于一个区间找到对应的 \(\log n\) 级别的组对应的节点，向这些节点连边即可。细节有一些，比如要建两棵线段树，分别对应区间连入和区间连出；对应的叶子节点要建双向边等。
标签：线段,板子,序列,prufer,节点,性质 From： https://www.cnblogs.com/Feyn/p/16940794.html