题解 P3830 【[SHOI2012]随机树】

· · 题解

第一问很好处理：设f_x表示有x个叶子节点的树的叶子节点平均深度

我们考虑在一个有x-1个叶子节点的树里随机选择一个叶子节点展开，那么树的叶子节点深度总和会增加f_{x-1}+2

所以f_x=\frac {f_{x-1}*(x-1)+f_{x-1}+2} x=f_{x-1}+\frac 2 x

第二问就比较难受了：

首先我们知道一个式子：

E(x)=∑^{+∞}_{i=1}P(i\leq x)

说人话就是随机变量x的期望为对于所有i，i\leq x的概率之和

我们设f[i][j]表示有i个叶子，树的深度\geq j的概率

转移时枚举左右子树有多少个叶子：

f[i][j]=\sum_{k=1}^{i-1}\frac 1 {i-1}(f[k][j-1]+f[i-k][j-1]-f[k][j-1]*f[i-k][j-1])

（括号里的式子含义：左右只要一边深度\geq j-1即可，所以式子展开其实是f[k][j-1]*1+f[i-k][j-1]*1，但这样会计算两次两边都\geq j-1的情况，所以需要减掉）

最后答案即为\sum_{i=1}^{n-1}f[n][i]

代码:

#include<cstdio>
#include<iostream>
using namespace std;
int p,n;
double f[110],dp[110][110],ans;
int main()
{
    scanf("%d%d",&p,&n);
    if (p==1)
    {
        f[1]=0;
        for (int i=2;i<=n;i++) f[i]=f[i-1]+2.0/i;
        printf("%.6f",f[n]);
    }
    else
    {
        for (int i=1;i<=n;i++) dp[i][0]=1;
        for (int i=2;i<=n;i++)
            for (int j=1;j<i;j++)
            {
                for (int k=1;k<i;k++)
                    dp[i][j]+=dp[k][j-1]+dp[i-k][j-1]-dp[k][j-1]*dp[i-k][j-1];
                dp[i][j]/=(i-1);
            }
        for (int i=1;i<n;i++) ans+=dp[n][i];
        printf("%.6f",ans);
    }
}