【洛谷P3830】随机树

题目

题目链接：https://www.luogu.com.cn/problem/P3830

思路

期望\(dp\)萌新。

先考虑第一问。我们设\(f[i]\)表示有\(i\)个叶节点时，叶子结点的期望深度。
我们知道所有叶子结点的期望深度之和为\(f[i]\times i\)。那么当有\(i-1\)个叶子结点时，我们在叶子结点中随机展开一个，叶子深度之和就变为了\(f[i-1]\times (i-1)+2\times (dep[x]+1)-dep[x]\)。
其中\(2\times (dep[x]+1)-dep[x]=dep[x]+2\)，而\(dep[x]\)的期望为\(f[i-1]\)，所以叶子深度之和就是\(f[i-1]\times i+2\)
所以有
\[f[i]\times i=f[i-1]\times i+2\]
即
\[f[i]=f[i-1]+\frac{2}{i}\]

第二问。我们设\(f[i][j]\)表示有\(i\)个叶子结点，树的深度不小于\(j\)的概率。
那么有
\[f[i][j]=\sum^{i}_{j=1}\sum^{i}_{k=1}\frac{f[k][j-1]+f[i-k][j-1]-f[k][j-1]\times f[i-k][j-1]}{i-1}\]

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=110;
double ans,f[N][N];
int n,opt;

int main()
{
    scanf("%d%d",&opt,&n);
    if (opt==1)
    {
        f[2][1]=1.0;
        for (int i=3;i<=n;i++)
            f[i][1]=f[i-1][1]+2.0/i;
        printf("%0.6lf",f[n][1]);
    }
    else
    {
        f[1][0]=f[2][0]=f[2][1]=1.0;
        for (int i=3;i<=n;i++)
        {
            f[i][0]=1.0;
            for (int j=1;j<i;j++)
            {
                for (int k=1;k<i;k++)
                    f[i][j]+=f[k][j-1]+f[i-k][j-1]-f[k][j-1]*f[i-k][j-1];
                f[i][j]/=(double)(i-1);
            }
        }
        for (int i=1;i<n;i++)
            ans+=f[n][i];
        printf("%0.6lf",ans);
    }
    return 0;
}