做ZR题触及了知识盲区()

Prufer序列与Caylay定理

不特殊说明均指有标号无根树.

Prufer序列

对于一个有标号无根树, 其prufer序列是, 每次删掉一个编号最小的叶子, 然后在序列上push_back这个叶子连向的点, 直到只有两个点.

于是Prufer序列的特征(不好意思叫性质):

• 长度是 $n-2$ .
• 最后留下的两个点中一个是Prufer序列上最后一个点, 另一个是 $n$ .
• 每个点出现次数为度数-1.

于是发现显然可以直接对着序列重建树, 倒着做就行, 所以它是有标号无根树与序列的双射.

Caylay定理

1. $n$ 个点构成的树的方案数为 $n^{n-2}$ .

Prufer序列, 每个位置是在 $1\ldots n$ 中, 长 $n-2$ .

2. $n$ 个点, 和指定的 $k$ 个点, 做出 $k$ 棵树的森林使得 $k$ 个点都不在同一棵树立的方案树为 $kn^{n-k-1}$ .

考虑不指定这 $k$ 个点, 而是直接算最后除以 $\binom{n}{k}$ , 那么为了保证每一个 $k$ 子集只被算了一次, 钦定这 $k$ 个点为其所在生成树的根, 那么因为我们只会算一棵树的所以钦定 $0$ 为全局的根, $0$ 向其他所有根连边, 于是我们就要求prufer序列满足其中出现了 $k-1$ 个0, 方案数就是 $\binom{n-1}{k-1}\times n^{n-k}$ , 再除以 $\binom{n}{k}$ 即可.

3. $Graph(n, m)$ 有 $K$ 个连通块, 要添加 $k-1$ 条边使得其连通的方案数.

$n^{k-2}\times \prod_{i=1, k} s_i$ , 其中 $s_i$ 表示第 $i$ 个连通块的大小.