Prufer序列模板

用于树上计数问题。

father -> prufer

查看代码

for (int i = 1; i < n; i++)
    read(f[i]), ++d[f[i]];
for (int i = 1, j = 1; i < n - 1; i++, j++)
{
    for (; d[j]; j++);
    p[i] = f[j];
    for (; i < n - 1 && !(--d[p[i]]) && p[i] < j; i++)
        p[i + 1] = f[p[i]];
}

prufer -> father

查看代码

for (int i = 1; i < n - 1; i++)
    read(p[i]), d[p[i]]++;
p[n - 1] = n;
for (int i = 1, j = 1; i < n; i++, j++)
{
    for (; d[j]; j++);
    f[j] = p[i];
    for (; i < n && !(--d[p[i]]) && p[i] < j; i++)
        f[p[i]] = p[i + 1];
}

Cayley 定理：

• $n$ 个点有标号无根树有 $n ^ {n - 2}$ 个；
• $n$ 个点有标号有根树有 $n ^ {n - 1}$ 个；
• $n$ 个点有标号有根森林有 $(n + 1) ^ {n - 1}$ 个。

拓展 Cayley 定理：

• $n$ 个点 $k$ 棵树的有标号有根森林有 $\binom n k k n ^ {n - k - 1}$ 个。

点有点权 $w _ i$ ，边权为两点点权之积，树的权值为所有边权之积，那么所有树的权值和为 $(\prod w _ i) (\sum w _ i) ^ {n - 2}$ 。

对于每个点度数为 $d _ i$ 的无根树，个数为 $\frac {(n - 2) !} { \prod (d _ i - 1) ! }$ 。

$n$ 个点的完全图生成树的个数为 $n ^ {n - 2}$ ，左部 $n$ 个点、右部 $m$ 个点的完全二分图的生成树个数为 $m ^ {n - 1} n ^ {m - 1}$ 。