题目大意

题解

这个题好神啊 考试的时候我只写了$30$分的阶乘算法
这个题$50$分就是说我们状压一下
先把所有点的深度排个序 然后每个深度最先出现的点是$1$其余是$0$,然后我们发现每次转移就是一些变化 直接转移就行了
(其实这个题原题好像这个就是正解了QAQ)
考虑$100$分的做法
我们用$h[i][j]$表示当前考虑了$i$个点,其中有$j$个点在第一棵树里面的概率(因为总的状态显然是一个森林)
这样的话我们的$h[i][j]$会由$h[i-1][j]$和$h[i-1][j-1]$得到
其中前者是说第$i$个点没有放到第一棵树里面 后者反之
这样的话我们的转移方程就是
$h[i][j]=h[i-1][j-1] * (j-1) * inv[i]+h[i-1][j] * (i-j) * inv[i]$
其中$ * inv[i]$表示概率
然后这些东西我们预处理出来
接下来我们表示两个新的状态$g[i][j],f[i][j]$
这两个东西表示
$g[i][j]$:$i$个点的森林,最大的深度不超过$j$的概率
$f[i][j]$:$i$个点的树,最大的深度不超过$j$的概率
这样的话这两个值可以彼此转移
首先$f[i][j]=g[i-1][j-1]$这个转移可以想成用一个点把一个森林连起来
然后$g[i][j]= \sum _ {k=1}^{i} h[i][k] * g[i-k][j] * f[k][j]$
这个看看大概就都会了
然后最后每个深度$i$的答案就是$f[n][i]-f[n][i-1]$
这是概率 再$ * i$就好了

代码