首页 > 其他 > 详细

Cayley公式

时间:2019-03-04 17:40:34      阅读:165      评论:0      收藏:0      [点我收藏+]

维基百科

Cayley公式:一个完全图K_n有n^(n-2)棵生成树,换句话说n个节点的带标号的无根树有n^(n-2)个。

Prufer编码:给定一棵带标号的无根树,找出编号最小的叶子节点,写下与它相邻的节点的编号,然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止。

一颗无根树与一个Prufer编码对应

广义 CayleyCayley 定理:

n个标号节点形成一个有 k 颗树的森林,使得给定的 k 个点没有两个点属于同一颗树的方案数为kn^(nk1).

不会证明。

例题

题意:所有边权都是 [1,m] 中的整数的所有 n 个点的树中,点 a 到点 b 的距离恰好是 m 的有几个。

题解:参考这个懒得写

code

Cayley公式

原文:https://www.cnblogs.com/lhclqslove/p/10471671.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!