地产网站开发公司,杭州网站建设ttmwl,成都网络推广公司排行榜,做网站被网警找Prufer序列
起源于对 C a y l e y Cayley Cayley定理的证明#xff0c;但是其功能远不止于此 现在考虑将一棵n个节点的树与一个长度为n-2的prufer序列构造对应关系 T r e e − P r u f e r : Tree-Prufer: Tree−Prufer: ①从树上选择编号最小的叶子节点#x…Prufer序列
起源于对 C a y l e y Cayley Cayley定理的证明但是其功能远不止于此 现在考虑将一棵n个节点的树与一个长度为n-2的prufer序列构造对应关系 T r e e − P r u f e r : Tree-Prufer: Tree−Prufer: ①从树上选择编号最小的叶子节点序列的下一位为其父节点的编号。 ②删去该叶子节点。 ③重复①和②直到树只剩下两个节点此时序列的长度刚好为 n−2 。 P r u f e r — T r e e : Prufer—Tree: Prufer—Tree: ①选择编号最小的叶子节点即未出现在序列中的节点其父节点就是序列的第 i i 初始为1个元素。 ②由性质可得其父节点的度数为其出现次数1。将该叶子节点删去其父节点度数-1。若度数变成1则父节点也成为叶子节点。 ③将 i 加一然后重复①和②直到序列的每一个元素都使用完毕。
ll p[N];
ll d[N];//度数
ll f[N];//连边
ll ans0;
void Prufer_To_Tree(ll n)
{//f记录1-n-1的连边情况for(int i1;in-2;i) cinp[i],d[p[i]];p[n-1]n;for(int i1,j1;in;i,j){while(d[j]) j;f[j]p[i];//把最小的叶往prufer序列第一个点上接 对应减掉度数while(in!--d[p[i]]p[i]j) f[p[i]]p[i1],i;//如果序列第一个点减掉度数后产生了新的更小的叶 就往序列下一个点上接}for(int i1;in;i) ans^1ll*i*f[i];
}
void Tree_To_Prufer(ll n)
{for(int i1;in;i) cinf[i],d[f[i]];for(int i1,j1;in-2;i,j){while(d[j]) j;p[i]f[j];while(in-2!--d[p[i]]p[i]j) p[i1]f[p[i]],i;}for(int i1;in-2;i) ans^1ll*i*p[i];
}由此我们发现两者是一一对应的也就是双射所以大小为n的有标号无根树的个数等于长度为 n − 2 n-2 n−2的prufer序列的个数自然为 n n − 2 n^{n-2} nn−2 C a y l e y Cayley Cayley定理得证
Prufer序列的性质
由Prufer序列构造的过程我们可以发现其具有两个显而易见的性质。 构造完后剩下的两个节点里一定有一个是编号最大的节点。 对于一个 n 度的节点其必定在序列中出现 n−1 次。因为每次删去其子节点它都会出现一次最后一次则是删除其本身。一次都未出现的是原树的叶子节点。
应用
1、无向完全图的不同生成树数 n n − 2 n^{n−2} nn−2 。
2、 n 个点的无根树计数
同上问题。
3、 n 个点的有根树计数
对每棵无根树来说每个点都可能是根故总数为 n n − 2 × n n n − 1 n^{n−2}×nn^{n−1} nn−2×nnn−1 。
4、 n 个点每点度分别为 d i d_i di 的无根树计数
显然就是一个多重集答案为 ( n − 2 ) ! ∏ i 1 n d i − 1 \frac{(n-2)!}{\prod_{i1}^{n}d_i-1} ∏i1ndi−1(n−2)!
5、 有标号的完全二分图 K n , m K_{n,m} Kn,m的生成树个数为 n m − 1 m n − 1 n^{m-1}m^{n-1} nm−1mn−1:
考虑将其生成树的prufer序列按照原本顺序分成 f i ≤ n , f i n f_i\leq n,f_in fi≤n,fin两部分。
对于 f i ≤ n f_i\leq n fi≤n的部分一定是删去某个标号 n n n的点之后留下 f i f_i fi的因为这是一张二分图。所以该部分的点一定恰好有 m − 1 m-1 m−1个右部有m个点整张图删完之后一定在左右部各留下一个点所以右部一共要删去 m − 1 m-1 m−1个点 f i n f_in fin部分同理。
所以此时还是可以用一个prufer序列与合法生成树对应故方案数为 n m − 1 m n − 1 n^{m-1}m^{n-1} nm−1mn−1
Tips:
一般要特判n1的情况
例题
Valuable Forests
大意
定义一个树的权值为其所有节点的度数的平方和森林的权值为所有树的权值和。求大小为n的所有有标号森林的权值和
思路 f i f_i fi表示大小为i的所有有标号森林的权值和也就是答案
考虑对于最后一个点所在的树的大小为k的情况
则 f n ∑ k 1 n ( n − 1 k − 1 ) f n − k m k ( n − 1 k − 1 ) g k h n − k f_n\sum_{k1}^{n}\binom{n-1}{k-1}f_{n-k}m_k\binom{n-1}{k-1}g_kh_{n-k} fn∑k1n(k−1n−1)fn−kmk(k−1n−1)gkhn−k
其中 m i m_i mi表示大小为 i i i的有标号无根树的个数 g i g_i gi表示大小为 i i i的所有有标号无根树的权值和 h n − k h_{n-k} hn−k表示大小为 n − k n-k n−k的森林的数量。 ( n − 1 k − 1 ) \binom{n-1}{k-1} (k−1n−1)是因为枚举的k的含义是n所在树的大小我要从剩下 n − 1 n-1 n−1个点里面选 k − 1 k-1 k−1个点。如果不这样枚举的树的组合就会算重。 m n m_n mn很简单 n 1 n1 n1时 m 1 1 m_11 m11否则 m n n n − 2 m_nn^{n-2} mnnn−2
对于 g n g_n gn,我们枚举所有度数为i的贡献
转化到prufer序列中看这个问题度数为i表示出现了 i − 1 i-1 i−1次所以强制选定对应的数字以及位置剩下的 n − 1 n-1 n−1个数随便放 g n ∑ i 1 n − 1 i 2 n ( n − 2 i − 1 ) n − 1 n − 1 − i g_n\sum_{i1}^{n-1}i^2n\binom{n-2}{i-1}{n-1}^{n-1-i} gn∑i1n−1i2n(i−1n−2)n−1n−1−i h n h_n hn的更新思路和 f f f差不多枚举最后一个点所在的树的大小即可 h n ∑ i 1 n ( n − 1 i − 1 ) h n − i m i h_n\sum_{i1}^{n}\binom{n-1}{i-1}h_{n-i}m_i hn∑i1n(i−1n−1)hn−imi
cf 156D
大意
给定n个点以及m条连边记最少添加T条边使得整张图连通问有多少种恰好添加T条边的方案使得图连通
思路:
记当前连通块个数为k则Tk-1
对于每一个连通块其大小为 a i a_i ai如果其度数为 d i d_i di的话我们可以在以连通块为单位的情况下得到生成树个数为 ( k − 2 d 1 − 1 , d 2 − 1... d k − 1 ) \binom{k-2}{d1-1,d2-1...d_k-1} (d1−1,d2−1...dk−1k−2)
对于每一个连通块固定连边的标号顺序比如第1条边来自标号最小的连通块依次类推那么此时总方案数为 ( k − 2 d 1 − 1 , d 2 − 1... d k − 1 ) ∗ ∏ i 1 k a i d i \binom{k-2}{d1-1,d2-1...d_k-1}*\prod_{i1}^{k}a_i^{d_i} (d1−1,d2−1...dk−1k−2)∗∏i1kaidi,因为每一条边都可以有 a i a_i ai种选择
所以答案为 ∑ ∑ d i k − 2 ( k − 2 d 1 , d 2... d k ) ∗ ∏ i 1 k a i d i 1 ∑ ∑ d i k − 2 ( k − 2 ) ! ∏ i 1 k d i ! ∗ ∏ i 1 k a i d i 1 \sum_{\sum d_ik-2}\binom{k-2}{d1,d2...d_k}*\prod_{i1}^{k}a_i^{d_i1}\sum_{\sum d_ik-2}\frac{(k-2)!}{\prod_{i1}^{k} d_i!}*\prod_{i1}^{k}a_i^{d_i1} ∑∑dik−2(d1,d2...dkk−2)∗∏i1kaidi1∑∑dik−2∏i1kdi!(k−2)!∗∏i1kaidi1 ( k − 2 ) ! ∏ i 1 k a i ( ∑ ∑ i 1 k d i k − 2 ∏ i 1 k a i d i d i ! ) (k-2)!\prod_{i1}^{k} a_i(\sum_{\sum_{i1}^{k} d_ik-2}\prod_{i1}^{k}\frac{a_i^{d_i}}{d_i!}) (k−2)!∏i1kai(∑∑i1kdik−2∏i1kdi!aidi)
注意到 ( k − 2 ) ! ∏ i 1 k a i (k-2)!\prod_{i1}^{k} a_i (k−2)!∏i1kai是一个常数我们只用看后面
记生成函数 f x ∑ i 0 inf x i i ! e x f_x\sum_{i0}^{\inf}\frac{x_i}{i!}e^x fx∑i0infi!xiex
不难发现后面其实是k个函数 f a i f_{a_i} fai的卷积的某一项,故后面部分的答案为 [ x k − 2 ] ∏ i 1 k e a i x [ x k − 2 ] e n x n k − 2 ( k − 2 ) ! [x^{k-2}]\prod_{i1}^{k}e^{a_ix}[x^{k-2}]e^{nx}\frac{n^{k-2}}{(k-2)!} [xk−2]∏i1keaix[xk−2]enx(k−2)!nk−2
所以最终答案为 n k − 2 ∏ i 1 k a i n^{k-2}\prod_{i1}^{k}a_i nk−2∏i1kai
