【BZOJ2830/洛谷3830】随机树（动态规划）

【BZOJ2830/洛谷3830】随机树（动态规划）

题面

洛谷

题解

先考虑第一问。
第一问的答案显然就是所有情况下所有点的深度的平均数。
考虑新加入的两个点，一定会删去某个叶子，然后新加入两个深度为原先叶子(+1)的点。
那么新加入的叶子的深度的期望是未加入之前的期望+1，假设(f_i)为(i)个点的期望。
那么(f_i=(f_{i-1}*({i-1})-f_{i-1}+2*(f_{i-1}+1))/i=f_{i-1}+2/i)
含义就是平均的深度乘上点的个数等于深度总和，减去删去的点的深度，加入两个新的深度为原先点(+1)的点。

考虑第二问
不难想到一个状态(f[i][j])表示拥有(i)个节点，深度为(j)的概率。
那么答案就是(sum_{i=0}^nf[n][i]*i)
这个转移不难，我们根节点已经固定，并且它一定拥有左右子树，我们转移的时候分开考虑左右子树，然后再在根节点的位置合并，即

[f[i][max(k,l)+1] ightarrow f[j][k]*f[i-j][l]/(i-1) ]

除掉(i-1)的原因是一开始我们直接把左右儿子都当成整棵树来看，所以最终合并的时候要把总方案除掉。

还有一种做法，大同小异，然而复杂度更优秀。
设(f[i][j])表示(i)个叶子的树，深度至少为(j)的概率。
转移和上面的东西类似，容斥去重。

[f[i][j]=frac{1}{i-1}sum f[k][j-1]*1+f[i-k][j-1]*1-f[i][j-1]*f[i-k][j-1] ]

答案是(sum f[n][i])

#include<iostream>
#include<cstdio>
using namespace std;
int n,Q;
double ans,f[101][101];
int main()
{
	cin>>Q>>n;
	if(Q==1)
	{
		for(int i=2;i<=n;++i)
			ans+=2.0/i;
		printf("%.6lf
",ans);
	}
	else
	{
		for(int i=1;i<=n;++i)f[i][0]=1;
		for(int i=2;i<=n;++i)
			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])/(i-1);
		for(int i=1;i<=n;++i)ans+=f[n][i];
		printf("%.6lf
",ans);
	}
	return 0;
}