Luogu3830 随机树

题面

简化题意

一个初始情况只有根的二叉树，每次随机选一个叶子挂上一对左右儿子，直到叶子数为 $n$。求所有叶子平均深度的期望和树高的期望。

$n\leq 100$。

题解

第一问

设 $f_i$ 表示已经建了 $i$ 个叶子，所有叶子的深度平均值。则 $i$ 个叶子的树叶子深度之和为 $f_i\times i$。

考对于某个深度为 $dep_i$ 的点 $i$，给它挂一对儿子会产生的影响。不难得到总的贡献为 $dep_i+2$。同时叶子数量多 。对于 $i-1$ 个叶子，选到一个的概率是 $\frac{1}{i-1}$，所以有：

$\begin{aligned} f_i\times i &=f_{i-1}\times(i-1)+\sum_j^{i-1}\frac{dep_j+2}{i-1} \\ &=f_{i-1}\times i-f_{i-1}+\sum_j^{i-1}\frac{dep_j}{i-1}+\frac{2(i-1)}{i-1} \\ \end{aligned}$

其中 $\sum_j^{i-1}\frac{dep_j}{i-1}$ 为 $i-1$ 个叶子的平均深度，所以 $\sum_j^{i-1}\frac{dep_i}{i-1}=f_{i-1}$：

$f_i\times i=f_{i-1}\times i+2$

得到 $f_i=f_{i-1}+\frac{2}{i}$，初值 $f_1=0$，$\mathcal{O}(n)$ 递推即可。

第二问

• 四次方做法
• 三次方做法

设 $f_{i,j}$ 表示有 $i$ 个叶子，树高为 $j$，这样的树出现的概率：

$Ans=\sum_{i=1}^{n-1} f_{n,i}\times i$

枚举根节点的左子树内部的情况。设 $p_{i,j}$ 表示一共有 $i$ 个叶子，其中 $j$ 个在根的左子树的概率。因为根节点的深度为 $0$，所以下图绿色部分的深度，等于两个红色部分深度的较大值加 $1$。

因此我们枚举左子树的子树，当这两边有一边的深度为 $j-1$ 时，总的深度就是 $j$。所以有：

$f_{i,j}=\sum_{k=1}^{i-1}p_{i,k}\times\sum_{x=1}^{j}\sum_{y=1}^{j}f_{k,x}\times f_{i-k,y} [x=j-1 \lor y=j-1]$

因为后面两个 sigma 的条件是 $x,y$ 有一个满足是 $j-1$，所以没必要套起来。时间复杂度 $n^4$。

设 $p_{i,j}$ 表示一共有 $i$ 个叶子，其中 $j$ 个在根的左子树的概率，$f_{i,j}$ 表示有 $i$ 个叶子，且深度大于等于 $j$ 的概率。

考虑根的左儿子的两个子树的情况，只要有一边的深度大于等于 $j-1$，整个树的深度就大于等于 $j-1$。分别考虑左右子树是否有一边深度大于等于 $j-1$。注意两边都有可能大于等于 $j-1$，因此需要去除重复算的部分：

$f_{i,j}=\sum_{k=1}^{i-1}p_{i,k}\times(f_{k,j-1}+f_{i-k,j-1}-f_{k,j-1}\times f_{i-k,j-1})$

若 $p$ 能预处理或 $\mathcal O(1)$ 算，时间复杂度就是 $n^3$。考虑怎么算 $p$。

第一个 sigma 中枚举 $k$ 表示左子树的叶子个数。考虑左子树里有恰好 $k$ 个叶子的树如何生成。第一步是根挂叶子，然后左子树与右子树以某种顺序挂叶子，只要左子树挂了 $k-1$ 次就够了。

顺序不影响叶子的个数，只要是 $k-1$ 次左边和 $i-k-1$ 从右边组成的挂节点顺序就可以了。因此一个组合数 $\binom{i-2}{k-1}$。

考虑左子树生成的方案数。$k$ 个叶子有 $(k-1)!$ 种方法。证明：设 $k$ 个叶子有 $a_k$ 种方法，而 $k$ 个叶子相当于 $k-1$ 个叶子的情况任选叶子挂新节点，有 $a_k=a_{k-1}\times(k-1)$。

同理，右子树叶子数为 $i-k$，生成的方案数为 $(i-k-1)!$。两种方法相乘，总共有 $(k-1)!(i-k-1)!$ 种方案。乘上前面求出的左右子树生成顺序的方案数 $\frac{(i-2)!}{(k-1)!(i-k-1)!}$。我们发现生成一个左子树有 $k$ 个叶子，右子树有 $i-k$ 个叶子的树的方案数为 $(i-2)!$，与 $k$ 没有什么关系了。

回到 $p$ 的定义，$p_{i,j}$ 表示一共有 $i$ 个叶子，其中 $j$ 个在根的左子树的概率。前面推出 $p_{i,j}$ 与 $j$ 无关。而左子树至少有一个叶子。因此左子树的叶子数有：$1,2,3,\cdots,i-1$ 几种可能。因为是等概率的，所以有 $p_{i,j}=\frac{1}{i-1}$：

$f_{i,j}=\sum_{k=1}^{i-1}\frac{f_{k,j-1}+f_{i-k,j-1}-f_{k,j-1}\times f_{i-k,j-1}}{i-1}$

初值 $f_{i,0}=1$。不难发现这样的递推是 $n^3$ 的。考虑求答案。

$n$ 个叶子的树，深度不超过 $n-1$。因此设 $g_{i,j}$ 表示有 $i$ 个叶子，深度等于 $j$ 的概率：

$Ans=\sum_{i=1}^{n-1} g_{n,i}\times i$

而且可以知道：

$f_{i,j}=\sum_{k=j}^{n-1} g_{i,k}$

因此对所有的 $f_{n,j}$ 求和：

$\begin{aligned} \sum_{i=1}^{n-1} f_{n,i} &=\sum_{i=1}^{n-1}\sum_{j=i}^{n-1} g_{n,j} \\ &=\sum_{i=1}^{n-1} g_{n,i}\times i \\ &=Ans \end{aligned}$

得出答案为 $\sum_{i=1}^{n-1} f_{n,i}$。

代码

采用 $n^3$ 做法。

#include<bits/stdc++.h>
using namespace std;
const int max_n=303;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}

int n,T;
double f1[max_n],f[max_n][max_n];

signed main(){
	T=read()-1,n=read();
	if(T){
		for(register int i=0;i<=n;++i)
			f[i][0]=1;
		for(register int i=1;i<=n;++i)
			for(register int j=1;j<=i-1;++j){
				f[i][j]=0;
				for(register int k=1;k<=i-1;++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.0;
		for(register int i=1;i<=n-1;++i)
			ans+=f[n][i];
		printf("%.6lf",ans);
	}
	else{
		f1[1]=0;
		for(register int i=2;i<=n;++i)
			f1[i]=f1[i-1]+2.0/i;
		printf("%.6lf",f1[n]);
	}
	return 0;
}