写在前面：在复健矩阵的时候发现了 [NOI2007]生成树计数 这个题，遂起兴研究生成树计数

个结点的环的生成树个数为

个结点的完全图的生成树个数为

第一句话很好理解，只要去除环中的任意一条边，就是一棵生成树

第二句话也叫 公式，证明需要用到 序列的东西，顺便提一嘴， 序列就是为证明 公式而诞生的

犹记两年前 讲题时给我们讲到过这个东西，但是已经忘掉了

Prufer Code

以下提到的树都是有标号无根树

每棵结点数大于 的树都对应唯一一个 序列，每个 序列也唯一对应一棵结点数大于 的树，两者为双射关系

由树构造 序列步骤如下：

  1. 找到叶子结点中编号最小的，记作 ，将 的父结点 加入序列
  2. 删去 结点
  3. 重复步骤 1. 和 2. ，直到整棵树只剩下两个结点，结束

显然，若整棵树有 个结点，那么该树对应的 序列长度应该为

由构造过程，可以得出两个结论：

  1. 结点 最后一定没有被删除
  2. 每个结点的度是序列中该结点出现次数

根据构造过程，相似地，可以得出由 序列构造树的方法：

  1. 根据度数为 确定当前的叶子结点，找出叶子结点中编号最小的结点，记作 ，将 的父结点设为序列中第一个没有遍历过的结点
  2. 删去 ， 度数 ，如果 度数为 ，那么把其加入叶子节点集合中
  3. 重复 1. 和 2. ，最后会剩下两个叶子结点，将其连接，结束

由每一步构造的唯一性以及每一步反构造的唯一性，由反证法可以得出

  1. 不存在两个 序列对应同一棵树
  2. 不存在两棵树对应同一个 序列

设 为所有树构成的集合， 为所有 序列构成的集合，由 1. 得 ，由 2. 得 ，即 ，得证

若要钦定根，最后可以添加一个根节点，序列长度变为 ，相似地，可以唯一确定一棵有标号有根树

更好的构造与反构造方法

模板

用代码模拟构造和反构造当然可以用小根堆，时间复杂度

还有一种更为快速的方法

构造：

  1. 找到编号最小的叶子结点 ，父结点 加入序列
  2. 若删去 后， 变为叶子结点，且编号比 小，则 为当前编号最小的叶子结点，直接令 为 ，重复操作 1. 和 2.
  3. 若不满足 2. ，将 自增，直到找到下一个未删除的叶子结点

最多自增 次，时间复杂度 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int p;
for(int i=1;i<=n;i++) if(d[i]==1){p=i;break;}

vector<int> prufer;
int l=p;
while(prufer.size()<n-2){
    int f=fa[l];
    prufer.push_back(f);
    d[f]--;
    if(d[f]==1&&f<p) l=f;
    else{
        p++;
        while(d[p]!=1) p++;
        l=p;
    }
}

反构造：同上

看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int p;
for(int i=1;i<=n;i++) if(d[i]==1){p=i;break;}

int l=p;
for(int i=1;i<=n-2;i++){
    int f;
    f=fa[l]=prufer[i];
    d[f]--;
    if(d[f]==1&&f<p) l=f;
    else{
        p++;
        while(d[p]!=1) p++;
        l=p;
    }
}
fa[l]=n;//最后剩下的两个点

OK

学完 序列后就能证明 公式了，由于每个序列唯一对应一棵树，那么长度为 的序列的总个数就是 个点的完全图的生成树个数，也就是 个

有根树对应 序列长度为 ，数量为 个

来点数学

如果给定 并固定每个点的度数，那么能形成的有标号无根树有多少？

考虑 序列，先阶乘再去重就好啦，设第 个点度数为 ，答案是

板子

完全二分图生成树个数？

左部点 个，右部点 个

构造 序列最后剩下的两个点一定是左部点一个右部点一个，考虑删去的点，删去一个左部点一定会往序列填一个右部点，删去一个右部点一定会往序列填一个左部点，最后的序列中左部点的数量为 个，右部点数量为 个， 序列共有 个，答案也是这个

以上 都需要特判o

当时找了几道题，我去做做

CF917D（这道题也是曾经 佬课件上的一道题）但是我不会二项式反演

ARC106F（需要生成函数，不会捏）

牛客挑战赛48C（这个可以写）

TopCoder SRM697 div1 hard 是这道 （看不懂所以不写）

把一些参考放在这里

《Tree-structured Data Regeneration with Network Coding in Distributed Storage Systems》

【朝夕的ACM笔记】图论-Prufer序列 - 知乎 (zhihu.com)

Prufer 序列 - Achtoria - 博客园 (cnblogs.com)

本文采用CC-BY-SA-3.0协议，转载请注明出处
作者: wsy_jim