生成树计数-prufer

cwy posted @ 2018年1月02日 17:51 in 板子 , 38 阅读

https://www.cnblogs.com/dirge/p/5503289.html

BZOJ1005

确定每个点度数后容易求出有多少种不同的无根树。

https://loj.ac/problem/6044

硬点一些点作为奇层点,一些点作为偶层层,方案数为C(n-1,k-1)。

令S(x,y)表示左边x个点右边y个点的二分图的生成树计数。

ans=C(n-1,k-1)*S(k,n-k)

考虑用prufer推S(x,y):

最后剩下的两个点肯定一个是左边的,一个是右边的。

因为我们已经确定了左边x个点的标号和右边y个点的标号,所以我们进行求prufer序列这个操作的时候,每次删掉的点是哪一个是确定的,只要考虑写入prufer的数是哪个,如果是删除左边,那么prufer中新增的数有y-1种可能,如果是删除右边,那么prufer中新增的数有x-1种可能,所以S(x,y)=x^(y-1)*y^(x-1)。

https://loj.ac/submission/52865


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter