【学习笔记】Prufer序列

Prufer序列

起源于对$Cayley$定理的证明，但是其功能远不止于此
现在考虑将一棵n个节点的树与一个长度为n-2的prufer序列构造对应关系

• $Tree->Prufer:$

  ①从树上选择编号最小的叶子节点，序列的下一位为其父节点的编号。

  ②删去该叶子节点。

  ③重复①和②，直到树只剩下两个节点，此时序列的长度刚好为 n−2 。

• $Prufer—>Tree:$

  ①选择编号最小的叶子节点（即未出现在序列中的节点），其父节点就是序列的第 i （ i 初始为1）个元素。

  ②由性质可得，其父节点的度数为其出现次数+1。将该叶子节点删去，其父节点度数-1。若度数变成1，则父节点也成为叶子节点。

  ③将 i 加一，然后重复①和②，直到序列的每一个元素都使用完毕。

ll p[N];
ll d[N];//度数
ll f[N];//连边
ll ans=0;
void Prufer_To_Tree(ll n)
{//f记录1-n-1的连边情况for(int i=1;i<=n-2;++i) cin>>p[i],d[p[i]]++;p[n-1]=n;for(int i=1,j=1;i<n;++i,++j){while(d[j]) j++;f[j]=p[i];//把最小的叶往prufer序列第一个点上接 对应减掉度数while(i<n&&!--d[p[i]]&&p[i]<j) f[p[i]]=p[i+1],i++;//如果序列第一个点减掉度数后产生了新的更小的叶 就往序列下一个点上接}for(int i=1;i<=n;++i) ans^=1ll*i*f[i];
}
void Tree_To_Prufer(ll n)
{for(int i=1;i<n;++i) cin>>f[i],d[f[i]]++;for(int i=1,j=1;i<=n-2;++i,++j){while(d[j]) j++;p[i]=f[j];while(i<=n-2&&!--d[p[i]]&&p[i]<j) p[i+1]=f[p[i]],i++;}for(int i=1;i<=n-2;++i) ans^=1ll*i*p[i];
}

由此我们发现两者是一一对应的，也就是双射，所以大小为n的有标号无根树的个数等于长度为$n-2$的prufer序列的个数，自然为$n^{n-2}$，$Cayley$定理得证

Prufer序列的性质

由Prufer序列构造的过程，我们可以发现其具有两个显而易见的性质。

• 构造完后剩下的两个节点里，一定有一个是编号最大的节点。

• 对于一个 n 度的节点，其必定在序列中出现 n−1 次。因为每次删去其子节点它都会出现一次，最后一次则是删除其本身。一次都未出现的是原树的叶子节点。

应用

1、无向完全图的不同生成树数：

$n^{n-2}$ 。

2、 n 个点的无根树计数：

同上问题。

3、 n 个点的有根树计数：

对每棵无根树来说，每个点都可能是根，故总数为 $n^{n-2}\times n=n^{n-1}$ 。

4、 n 个点，每点度分别为 $d_i$ 的无根树计数：

显然就是一个多重集，答案为$\frac{(n-2)!}{{\prod }_{i=1}^n{d}_i-1}$

5、 有标号的完全二分图$K_{n,m}$的生成树个数为$n^{m-1}{m}^{n-1}$:

考虑将其生成树的prufer序列按照原本顺序分成$f_i\le n,f_i>n$两部分。

对于$f_i\le n$的部分，一定是删去某个标号$>n$的点之后留下$f_i$的，因为这是一张二分图。所以该部分的点一定恰好有$m-1$个（右部有m个点，整张图删完之后一定在左右部各留下一个点，所以右部一共要删去$m-1$个点）

$f_i>n$部分同理。

所以此时还是可以用一个prufer序列与合法生成树对应，故方案数为$n^{m-1}{m}^{n-1}$

Tips:

一般要特判n=1的情况

例题

Valuable Forests

大意：

定义一个树的权值为其所有节点的度数的平方和，森林的权值为所有树的权值和。求大小为n的所有有标号森林的权值和

思路：

$f_i$表示大小为i的所有有标号森林的权值和，也就是答案

考虑对于最后一个点所在的树的大小为k的情况

则$f_n={\sum }_{k=1}^n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)f_{n-k}{m}_k+\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)g_k{h}_{n-k}$

其中$m_i$表示大小为$i$的有标号无根树的个数，$g_i$表示大小为$i$的所有有标号无根树的权值和，$h_{n-k}$表示大小为$n-k$的森林的数量。$\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$是因为枚举的k的含义是n所在树的大小，我要从剩下$n-1$个点里面选$k-1$个点。如果不这样枚举的树的组合就会算重。

$m_n$很简单：$n=1$时$m_1=1$，否则$m_n=n^{n-2}$

对于$g_n$,我们枚举所有度数为i的贡献

转化到prufer序列中看这个问题，度数为i，表示出现了$i-1$次，所以强制选定对应的数字以及位置，剩下的$n-1$个数随便放

$g_n={\sum }_{i=1}^{n-1}{i}^{2}n\left(\genfrac{}{}{0ex}{}{n-2}{i-1}\right){n-1}^{n-1-i}$

$h_n$的更新思路和$f$差不多，枚举最后一个点所在的树的大小即可

$h_n={\sum }_{i=1}^n\left(\genfrac{}{}{0ex}{}{n-1}{i-1}\right)h_{n-i}{m}_i$

cf 156D

大意：

给定n个点以及m条连边，记最少添加T条边使得整张图连通，问有多少种恰好添加T条边的方案使得图连通

思路:

记当前连通块个数为k，则T=k-1

对于每一个连通块，其大小为$a_i$，如果其度数为$d_i$的话，我们可以在以连通块为单位的情况下得到生成树个数为$\left(\genfrac{}{}{0ex}{}{k-2}{d1-1,d2-\mathrm{1...}{d}_k-1}\right)$

对于每一个连通块，固定连边的标号顺序（比如第1条边来自标号最小的连通块，依次类推），那么此时总方案数为$\left(\genfrac{}{}{0ex}{}{k-2}{d1-1,d2-\mathrm{1...}{d}_k-1}\right)\ast {\prod }_{i=1}^k{a}_i^{d_i}$,因为每一条边都可以有$a_i$种选择

所以答案为${\sum }_{\sum d_i=k-2}\left(\genfrac{}{}{0ex}{}{k-2}{d1,d\mathrm{2...}{d}_k}\right)\ast {\prod }_{i=1}^k{a}_i^{d_i+1}={\sum }_{\sum d_i=k-2}\frac{(k-2)!}{{\prod }_{i=1}^k{d}_i!}\ast {\prod }_{i=1}^k{a}_i^{d_i+1}$
$=(k-2)!{\prod }_{i=1}^k{a}_i({\sum }_{{\sum }_{i=1}^k{d}_i=k-2}{\prod }_{i=1}^k\frac{a_i^{d_i}}{d_i!})$

注意到$(k-2)!{\prod }_{i=1}^k{a}_i$是一个常数，我们只用看后面

记生成函数$f_x={\sum }_{i=0}^{\inf }\frac{x_i}{i!}=e^x$

不难发现后面其实是k个函数$f_{a_i}$的卷积的某一项,故后面部分的答案为$[x^{k-2}]{\prod }_{i=1}^k{e}^{a_{i}x}=[x^{k-2}]e^{nx}=\frac{n^{k-2}}{(k-2)!}$

所以最终答案为$n^{k-2}{\prod }_{i=1}^k{a}_i$