【洛谷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} \]

具体原因请看这篇题解qwq，是看这篇题解的，直接把他的证明方法抠过来也不好。
试图掩盖自己太菜的事实qwqwqwq，不过这篇讲的是真的很好

代码

#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;
}