P3830 随机树题解

upd：一个转移的 $j,y$ 打反了，已更正。此外修复了部分错别字，图床换源。

题目大意

一个初始情况只有根节点的二叉树，定义一个点的深度是这个点到根节点的路径边数，根节点深度为 $0$ ，一颗树的深度是所有点深度最大值。每次等概率地选择一个叶子，给它挂上一对左右儿子。直到叶子数量为 $n$ 。求：所有叶子节点平均深度的期望、整个树深度的期望，结果保留六位小数。（ $n\leqslant 300$ ）

原题目是 $n\leqslant 100$ ，我加强一下， $n\leqslant 300$ ，卡一卡 $n^4$ 暴力。

题解

平均深度

朴素的概率 DP（裸题）里面很少出现求一个平均的东西的概率。不过还是可以尝试用平时写裸 DP 的方式去试一波。设 $f_i$ 表示已经建了 $i$ 个叶子，此时所有叶子的深度平均值。我们知道平均深度等于总深度除以叶子数，所以 $i$ 个叶子的树叶子深度之和为 $f_i\times i$ 。

考虑我现在造了一个树，这个树上对于某一个节点 $i$ ，深度为 $dep_i$ ，给 $i$ 挂一对儿子会对总的深度造成多少影响。首先这个点不再是叶子了，所以要减掉一个 $dep_i$ ，然后多了俩叶子，深度是这个叶子 $+1$ 。因此加上 $2dep_i+2$ 。总的贡献为： $dep_i+2$ 。同时叶子数量多 $1$ ，从 $f_{i-1}$ 转移到 $f_i$ 。

$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$ （唯一的叶子就是根节点）， $\operatorname{O}(n)$ 递推即可。

总深度

四次方级别

第二问求总深度期望。我们沿着上一问的思路，发现只设一维不太好转移。所以设 $f_{i,j}$ 表示有 $i$ 个叶子，此时深度为 $j$ ，这样子的树出现的概率。我们都知道期望就是值与对应概率乘积的和。注意根节点深度为 $0$ ，根据定义式：

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

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

因此我们枚举左子树的子树（LeftLeftSon 和 LeftRightSon）情况，当这两边有一边的深度为 $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$ ，所以没必要套起来。时间复杂度 $\operatorname{O}(n^4)$ ，原题可以用这个糊过去。但是实际上还有 $n^3$ 的做法。

三次方级别

我们仍然假设 $p_{i,j}$ 表示一共有 $i$ 个叶子，其中 $j$ 个在根的左子树的概率。但是因为原本的 $f$ 状态行不太通，我们考虑换一下。

设 $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$ 可以用视为常数的方法算出来，那么时间复杂度就是 $\operatorname{O}(n^3)$ 。现在最大的问题就是怎么求出 $p$ 的值。

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

挂的顺序并不影响左右子树叶子的个数，因此只要是 $k-1$ 次左边和 $i-k-1$ 从右边组成的挂节点顺序就可以了。两次挂左边顺序不影响，因此就是 $(i-k-1)+(k-1)$ 次挂子树机会里面选择 $k-1$ 个当成挂左边的组合数，即： $C_{i-2}^{k-1}=\frac{(i-2)!}{(k-1)!(i-k-1)!}$ 。

然后考虑左子树生成的方案数。也就是求挂 $k-1$ 次叶子可以生成多少种 $k$ 个叶子的树。 $1$ 个叶子只有一种方法， $2$ 个叶子也只有一种方法。 $3$ 个叶子有 $2$ 种方法， $4$ 个叶子有 $6$ 种方法……我们发现 $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$ 几种可能。因为是等概率的，所以我们得到：

\forall i,j,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}

初始值为 $\forall i,f_{i,0}=1$ 。不难发现这样的递推是 $\operatorname{O}(n^3)$ 的。最后还剩下一个问题，我已经求出来这些 $f$ 了，最后的答案又是什么？

回到 $f$ 的状态设计： $f_{i,j}$ 表示有 $i$ 个叶子，且深度大于等于 $j$ 的概率。我们知道 $n$ 个叶子的树，深度不超过 $n-1$ 。因此我们设 $g_{i,j}$ 表示有 $i$ 个叶子，深度等于 $j$ 的概率。根据上面 $n^4$ 做法：

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}$ 。

代码

都是推式子，程序实现没有很困难的地方。

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

P3830 随机树 题解

题目大意

题解

平均深度

总深度

四次方级别

三次方级别

代码

感谢您的支持，我会继续努力的!