(Prufer) 序列
( exttt{definition})
(Prufer) 序列序列可以将一个带标号 (n) 个结点的树用 ([1..n]) 中的 (n-2) 个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。
显然你不会想不开拿这玩意儿去维护树结构。这玩意儿常用组合计数问题上。
( exttt{Construction sequence})
Prufer 是这样建立的：每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 (n-2) 次后就只剩下两个结点，算法结束。
很容易想到用堆做到 (O(nlog n))
然而可以线性构造
以上摘自 oi-wiki
( exttt{nature})
- 在构造完 (Prufer) 序列后原树中会剩下两个结点，其中一个一定是编号最大的点 (n) 。
- 每个结点在序列中出现的次数是其度数减 (1) 。（没有出现的就是叶结点）
( exttt{Rebuild the tree})
重建树的方法是类似的。根据 (Prufer) 序列的性质，我们可以得到原树上每个点的度数。然后你也可以得到度数最小的叶结点编号，而这个结点一定与 (Prufer) 序列的第一个数连接。然后我们同时删掉这两个结点的度数。
每次我们选择一个度数为 (1) 的最小的结点编号，与当前枚举到的 (Prufer) 序列的点连接，然后同时减掉两个点的度。到最后我们剩下两个度数为 (1) 的点，其中一个是结点 (n) 。就把它们建立连接。使用堆维护这个过程，在减度数的过程中如果发现度数减到 (1) 就把这个结点添加到堆中，这样做的复杂度是 (O(nlog n)) 的。
同理我们可以线性构造
在删度数的时侯会产生新的叶结点，于是判断这个叶结点与指针 (p) 的大小关系，如果更小就优先考虑它
( exttt{Gayley's formula})
凯莱定理
完全图 (K_n) 有 (n^{n-2}) 棵生成树。
怎么证明？方法很多，但是用 (Prufer) 序列证是很简单的。任意一个长度为 (n-2) 的值域 ([1..n]) 的整数序列都可以通过 (Prufer) 序列双射对应一个生成树，于是方案数就是 (n^{n-2}) 。
图的联通方案数
大家可以去看上文的链接
一个 (n) 个点 (m) 条边的带标号无向图有 (k) 个连通块。我们希望添加 (k-1) 条边使得整个图连通。求方案数。
这里只写出结论 (ans = n^{k-2}prod_{i=1}^k s_i)