Description：

开始有一棵只有一个根节点的树。每次随机选择一个叶子节点，为他添上左右子节点，求：

• 生成一棵有 $N$ 个叶节点的树，所有叶节点平均高度的期望。
• 生成一棵有 $N$ 个叶节点的树，树高的期望。

$1\leqslant n\leqslant 100$

Solution1：

我的做法

首先有一个性质，就是如果当前树的叶子节点数为 $i$ ，那么树的左子树的叶子节点数取 $[1,i-1]$ 的概率是完全相同的，都是 $\frac 1{i-1}$ 。

证明的话，总共有 $n$ 个叶子节点，设左子树有 $k$ 个叶子节点，左子树一定被选到了 $k-1$ 次，也就是说生成的方案数有 $C_{n-1-1}^{k-1}$ ，而每一种方案的概率一定可以表示成 $\frac\cdots2\times\frac\cdots 3\times\cdots\times\frac\cdots{n-1}$ ，分母是 $n-1$ 的阶乘，考虑分子，一定是 $(k-1$ 的阶乘 $)\times (n-k-1$ 的阶乘 $)$ ，所以这 $C_{n-2}^{k-1}$ 种方案的概率是相同的，都是 $\frac{(k-1)!(n-k-1)!}{(n-1)!}$ ，总概率就是 $\frac 1 {n-1}$ 。

第一问：

既然有这么一个性质，那么设 $f[i]$ 表示一棵有 $i$ 个叶子节点的树的叶子节点高度和的期望，由期望的线性性得 $ans=f[n]/n$ ，转移就枚举树的左子树的叶子节点个数 $k$ ，方程为 $f[i]=\frac{f[k]+k+f[i-k]+i-k}{i-1}$ 。时间复杂度 $O(n^2)$ 。

第二问：

设 $f[i][j]$ 表示 $i$ 个叶子节点的树深度为 $j$ 的概率，必须有一个子树深度为 $j-1$ ，转移枚举一下子树大小和另一棵子树的深度， $\begin{align}f[i][j]+=\frac 1{i-1}\sum_{k=1}^{i-1}\sum_{l=0}^{k-1}2\times f[k][j-1]\times f[i-k][l]\end{align}$ ，还要减掉多算的两个子树 $\begin{align}f[i][j]-=\frac 1{i-1}\sum_{k=1}^{i-1}f[k][j-1]\times f[i-k][j-1]\end{align}$ ，最后答案为： $$ ans=\sum_{i=1}^{n-1}f[n][i]\times i $$ 发现转移中 $l$ 和谁都没什么关系，可以前缀和优化一下，时间复杂度 $O(n^3)$ 。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int q,n;

#define MAXN 110

double f[MAXN];

double g[MAXN][MAXN],s[MAXN][MAXN];

int main()

{

	scanf("%d%d",&q,&n);

	if(q == 1)

	{

		f[2] = 2;

		for(int i = 3;i <= n;++i)

			for(int j = 1;j < i;++j)

				f[i] += (double)(f[j] + f[i - j] + i) / (i - 1);

		printf("%.6lf\n",f[n] / n);

	}

	else

	{

		g[1][0] = 1;

		for(int i = 0;i <= n;++i)s[1][i] = 1;

		for(int i = 2;i <= n;++i)

		{

			for(int j = 1;j < i;++j)

			{

				double res = 0;

				for(int k = 1;k < i;++k)

				{

					/*for(int l = 0;l <= j - 1;++l)

					{

						res += g[k][j - 1] * g[i - k][l];

					}*/

					res += g[k][j - 1] * s[i - k][j - 1];

				}

				res *= 2;

				for(int k = 1;k < i;++k)

				{

					res -= g[k][j - 1] * g[i - k][j - 1];

				}

				res /= (i - 1);

				g[i][j] = res;

			}

			for(int j = 1;j <= n;++j)

			{

				s[i][j] = s[i][j - 1] + g[i][j];

			}

		}

		double ans = 0;

		for(int i = 1;i <= n;++i)

		{

			ans += g[n][i] * i;

		}

		printf("%.6lf\n",ans);

	}

	return 0;

}

Solution2：

正解

第一问：

对于叶子 $v$ ，设他的深度为 $d_v$ ，那么扩展他会产生两个新的深度为 $d_v+1$ 的叶子，失去他这个深度为 $d_v$ 的叶子，增量为 $2\times (d_v+2)-d_v=d_v+2$ ，平均增量为 $f[i]+2$ 。考虑期望的增量，设 $f[i]$ 表示 $i$ 个叶子节点的树的叶子深度，期望的增量为：

$$ f[i]=\frac{f[i-1]\times(i-1)+f[i-1]+2}{i}=f[i-1]+\frac 2 i $$ 所以得到递推式 $f[i]=f[i-1]+\frac 2{i}$ 。

第二问：

设 $p[i][j]$ 表示 $i$ 个叶子节点的树深度为 $j$ 的概率，这题答案就是： $$ \sum_{i=1}^{n-1}i\times p[n][i]=\sum_{i=1}^{n-1}\sum_{j=1}^ip[n][i]=\sum_{j=1}^{n-1}\sum_{i=j}^{n-1}p[n][i] $$ 设 $f[i][j]$ 表示 $i$ 个叶子节点的树深度 $\geqslant j$ 的概率，那么答案就是： $$ \sum_{i=1}^{n-1}f[n][i] $$ 还是按照上面那个性质和转移，有： $$ f[i][j]=\frac 1{i-1}\sum_{k=1}^{i-1}(f[k][j-1]+f[i-k][j-1]-f[k][j-1]\times f[i-k][j-1]) $$ 时间复杂度 $O(n^3)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int q,n;

#define MAXN 110

double g[MAXN];

double f[MAXN][MAXN];

int main()

{

	scanf("%d%d",&q,&n);

	if(q == 1)

	{

		g[1] = 0;

		for(int i = 2;i <= n;++i)g[i] = g[i - 1] + 2.0 / i;

		printf("%.6lf\n",g[n]);

		return 0;

	}

	else

	{

		for(int i = 1;i <= n;++i)f[i][0] = 1.0;

		for(int i = 1;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];

				}

				f[i][j] /= (i - 1);

			}

		}

		double ans = 0;

		for(int i = 1;i < n;++i)

		{

			ans += f[n][i];

		}

		printf("%.6lf\n",ans);

	}

	return 0;

}