n个点的基环树数量

曾经终败给现在 2021-11-17 15:26 243阅读 0赞

某裴姓蒟蒻上午提了一个小问题(rt)。。然后他升华了。。升华之前感受到了神犇的力量。。。

--------------------

方法一：

g\[n\]\[k\]表示n个点,k条边的无向图（不一定连通）

f\[n\]\[k\]表示表示n个点,k条边的无向连通图

咕咕了。。。自己讲不清。。。O(n^4)

--------------------

方法二：

我们可以枚举环的大小，设为$i$,则可以从$ n$个中随意选$i$个点即$C\_n^i$，造出本质不同的环的数量为$(i-1)!$，但是会有翻转同构，所以要$/2$；

当n个点有k个连通块，把他们连成一棵树的方案数是：$ \\Pi sz\_i \\space\* n^\{k-2\}$

证明：把连通块看成点，$sz\_i$表示第$i$个连通块的点数

枚举$Prufer$序列，设$p\_i$为$Prufer$序列中的第$i$项，$q\_i$代表$i$在$Prufer$序列中的出现次数，

则有 $ \\Sigma\_\{Prufer\}\\space \\Pi sz\_i^\{q\_i+1\} \\space q\_i+1$相当于是$i$的度数，而每个点都有可能是连边的点，所以是$sz\_i^\{q\_i+1\}$

$\\Pi sz\_i \\space \\Sigma\_\{Prufer\}\\space \\Pi sz\_i^\{q\_i\}$

$\\Pi sz\_i \\space \\Sigma\_\{Prufer\} \\space \\Pi sz\_\{p\_i\}$

根据$Prufer$序列的性质，我们知道$Prufer$序列长$ k-2$并且每个位置都可以填$\[1,k\]$

所以根据乘法原理（或是说乘法分配律）可知：

$\\Sigma\_\{Prufer\} \\space \\Pi sz\_\{p\_i\}=\\Pi\_\{p=1\}^\{k-2\}\\Sigma\_\{i=1\}^k sz\_i$

所以有$\\Pi sz\_i \\space \\Pi\_\{p=1\}^\{k-2\}\\Sigma\_\{i=1\}^k sz\_i$，而$\\Sigma\_\{i=1\}^k sz\_i=n$

即$\\Pi sz\_i \\space n^\{k-2\}$

证毕

此时每个点的$sz$都是$1$，除了那个环的$sz$是$i$，共有$n-i+1$个点（连通块）

所以公式为$C\_n^i\*(i-1)!\*i\*n^\{n-i+1-2\}=C\_n^i\*i!\*n^\{n-i-1\}$

--------------------

咕了一天qwq2019.05.20

转载于:https://www.cnblogs.com/Jackpei/p/10888758.html

发表评论取消回复

表情：

评论列表（有 0 条评论，243人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】线索二叉树中为什么n个结点的二叉树中，有n+1和空指针

线索二叉树中为什么n个结点的二叉树中，有n+1和空指针：因为每个叶结点有2个空指针，而每个度为1的结点有1个空指针，则总的空指针数为 2 \ n0 + n1 而

痛定思痛。/ 2022年12月28日 01:44/ 0 赞/ 134 阅读

相关证明：对于一棵二叉树，若度为2的结点有n2个，叶子结点有n0个，则n0=n2+1

证明：证明：证明：设度为 0 的结点有 X 0 个，度为 1 的结点有 X 1 个，度为 2 的结点有 X 2 个，设度

左手的ㄟ右手/ 2022年10月13日 05:11/ 0 赞/ 158 阅读

相关 HDU 5874-Friends and Enemies（n个结点的无三元环的图的最大边数）

<table style="font-family:'Times New Roman'; word-wrap:break-word"> <tbody> <tr>

太过爱你忘了你带给我的痛/ 2022年09月25日 13:28/ 0 赞/ 16 阅读

相关树：求二叉树的高度和叶子结点数量

算法代码很简单都是用使用递归计算，大家把递归思想领悟到就ok了。二叉树高度算法 //求二叉树的高度采用递归的方式 void GetHeight(Bi

ゝ一世哀愁。/ 2022年05月31日 10:28/ 0 赞/ 235 阅读

相关 P4949 最短距离（树链剖分+树状数组+基环树）

[传送门][Link 1] 一个中午啊…… 本来打算用仙人掌搞的，后来发现直接基环树就可以了，把多出来的那条边单独记录为\\((dx,dy,dw)\\)，剩下的树剖

太过爱你忘了你带给我的痛/ 2022年01月12日 09:27/ 0 赞/ 219 阅读

相关【BZOJ4883】 [Lydsy1705月赛]棋盘上的守卫（最小生成树，基环树）

传送门 [BZOJ][] Solution 考虑一下如果把行,列当成点,那么显然这个东西就是一个基环树对吧. 直接按照\\(Kruscal\\)那样子搞就好了

小鱼儿/ 2021年12月20日 02:25/ 0 赞/ 224 阅读

相关 POI2012 Rendezvous 基环树+分类讨论

POI2012 Rendezvous [题目传送][Link 1] sol：首先把连通块划分出来。对于不在一个连通块的两点不能相会，否则必定能相会。在一个连

布满荆棘的人生/ 2021年11月23日 23:10/ 0 赞/ 240 阅读

相关 n个点的基环树数量

某裴姓蒟蒻上午提了一个小问题(rt)。。然后他升华了。。升华之前感受到了神犇的力量。。。 -------------------- 方法一： g\[n\]\[k\]表示n

曾经终败给现在/ 2021年11月17日 15:26/ 0 赞/ 244 阅读

相关 BZOJ3037/CH6401 创世纪（贪心 or 基环树dp）

题意：上帝手中有 N(N≤10^6) 种世界元素，每种元素可以限制另外1种元素，把第 i 种世界元素能够限制的那种世界元素记为 A\[i\]。现在，上帝要把它们中的一部分投放

小灰灰/ 2021年11月17日 09:16/ 0 赞/ 275 阅读

相关 [IOI2008/BZOJ1791 岛屿]（处理基环树的小技巧&基于bfs树形DP）

[IOI2008/BZOJ1791 岛屿][IOI2008_BZOJ1791] 题目大意是在一个基环树森林里求每一棵基环树的直径①的和。其实就是树的直径的基环树升级版。我

素颜马尾好姑娘i/ 2021年10月01日 04:20/ 0 赞/ 321 阅读