拓扑排序

考虑一棵无根树的生成方式：需要决定一个好的顺序从而达到不重不漏地生成所有 $n$ 个点的无根树。

类似有向无环图的拓扑排序，可以定义一种无根树的“拓扑排序”：每一轮将当前的叶子删去。这样可以很容易算出直径。设删除的轮数为 $r$，则当最终剩余一个孤点时，直径 $d=2r$，否则直径 $d=2r-1$。为了生成无根树，我们考虑进行逆操作，在当前的树上加叶子。在此之前，为了不重不漏地对无根树进行表示，我们考虑如下的唯一表示方法：设 $\text{dis}(x)$ 为节点 $x$ 在添加叶子过程中第几轮被添加上树的。对于$S=\{x\mid \text{dis}(x)=\text{const}\}$（也即同一层的节点），显然两棵有标号无根树同构但标号不同，当且仅当每个上述节点$x$的叶子节点的标号集合不同。我们总是将 $x$ 标号小的先行添加为其儿子。这样就不会出现因“两棵树本身同构，子节点编号集合相同导致重复计数的问题”。同时，为了方便、准确地计算，我们严格规定，新加入的 $k$ 个叶子节点在新树上就是全部的叶子节点。也即在旧树上的所有叶子节点在新树上至少有一个儿子。 （更多…）