(\)
(Description)
开始有一棵只有一个根节点的树。每次随机选择一个叶子节点，为他添上左右子节点，求：
- 生成一棵有(N)个叶节点的树，所有叶节点平均高度的期望。
- 生成一棵有(N)个叶节点的树，树高的期望。
约定根节点深度为(0)。
- (Nin [1,100])
(\)
(Solution)
果然还是太菜了只会抄题解 一道期望和概率间巧妙转化的好题。
(\)
第一问，平均的性质。
考虑每次扩展会随机选择一个叶节点，假设该叶节点的深度为(d_i)，对总叶节点深度和的贡献为((d_i+1) imes 2-d_i=d_i+2)。
等概率的选择，对深度的平均值增量之和(=frac{sum_{vin Leaf}d_v+2}{|Leaf|}=2+frac{sum_{vin Leaf}d_v}{|Leaf|}=2+ave)。所以一次扩展节点对期望的增量是(frac{ave+2}{|Leaf|})。
设(g[i])表示(i)个叶节点的深度平均值的期望，有
愉快的递推就好。
(\)
第二问，一种期望向概率的转化。
先考虑一种期望的表示方式。
关于证明，第一个等号显然成立。
第二个等号可以理解为，每个概率会被累加权值那么多次。
第三个等号可以理解为，越大的权值对应的概率被累加的越多，当可取的权值(+1)时，对应的所有小于它的数字都会累加上一份最大权的概率，但是小于最大权的数字个数为最大权(-1)，所以还需要累加上一份。
于是设(f_i)表示大于等于(i)的概率，进一步转化有
思考如何用这个性质求解树高期望。
将状态定义为一种基于最小值的设计方式。设(f[i][j])表示，有(i)个叶节点的树，树高(ge j)的期望，答案有
原理和上面是一样的。
考虑如何求(f)数组。有边界(f[i][0]=1.0 ig | iin [1,N])，因为任意时刻树高都会(ge 0)。
然后将任务下放到子树，左右子树的大小分布是等概率的，注意只要不是叶节点就一定左右子树都有。
所以只要有一棵深度合法就好，注意容斥掉两种情况重合时的部分。
好像漏掉了关于前面系数为什么是(frac{1}{i-1})的问题，发现问题被巨佬diss之后又上了一波百度，发现没有...
问了学长，证明大概是，考虑用(1)表示扩展了一个左子树内节点，用(0)表示扩展了一个右子树内的节点，那么生成一个(01)序列的概率就可以表示成，(frac{1}{2} imesfrac{2(1)}{3} imesfrac{3(2)(1)}{4} imes...)，分子部分表示选择一个左子树(/)右子树节点的概率。
比如生成树序列(00111)，概率可以表示成(frac{1}{2} imesfrac{2}{3} imesfrac{1}{4} imesfrac{2}{5} imesfrac{3}{6})，注意到交换(01)位置得到的式子的值不变。
为什么呢？因为分母部分一定是((i+1)!)，而分子部分一定是(k! imes (i-k)!)，表示两棵子树的生成过程。
于是一个左子树大小为(k)，右子树大小为(n-k)的树生成的概率就是(frac{k! imes(i-k)!}{(i+1)!}=frac{1}{i+1})，与(k)无关。
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 110
#define R register
using namespace std;
int n,q;
double g[N],f[N][N];
int main(){
scanf("%d%d",&q,&n);
if(q==1){
g[1]=0.0;
for(R int i=2;i<=n;++i) g[i]=g[i-1]+2.0/i;
printf("%.6lf",g[n]);
}
else{
for(R int i=1;i<=n;++i) f[i][0]=1.0;
for(R int i=2;i<=n;++i)
for(R int j=1;j<i;++j){
for(R 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.0;
for(R int i=1;i<=n;++i) ans+=f[n][i];
printf("%.6lf
",ans);
}
return 0;
}