LINK：随机树
非常经典的期望dp.
考虑第一问：设f[i]表示前i个叶子节点的期望平均深度。
因为期望具有线性性 所以可以由每个叶子节点的期望平均深度得到总体的。
(f[i]=(f[i-1]cdot (i-1)+(f[i-1]+1)cdot 2-f[i-1])/i=f[i-1]+2/i)
考虑第二问：可以设f[i][j]表示i个叶子节点树高恰好为j的概率。
转移即可 不过值得注意的是 P(i,k)有i个叶子k个被分给左子树的概率为1/(i-1) 这个可以通过计算得到。最终可以通过前缀和优化到n^3.
当然 根据最后答案的计算方式 我们可以将这个东西进行差分。
设f[i][j]表示i个叶子节点深度>=j的概率。
这样 (f[i][j]+=(f[k][j-1]+f[i-k][j-1]-f[k][j-1]cdot f[i-k][j-1])/(i-1))
最后除的那个 就是刚才得到的 k个节点被分到左子树的概率。
值得一提的是 初始化 f[i][0]=1. 这是必要的。
const int MAXN=110;
int Q,n;
db f[MAXN];//f[i]表示存在i个叶子节点的平均期望深度.
db g[MAXN][MAXN];//g[i][j]表示有i个节点深度>=j的概率.
int main()
{
freopen("1.in","r",stdin);
get(Q);get(n);
if(Q==1)
{
rep(2,n,i)f[i]=f[i-1]+2.0/i;
printf("%.6lf",f[n]);
}
else
{
g[1][0]=1;
rep(2,n,i)
{
g[i][0]=1;
rep(1,i-1,j)
{
rep(1,i-1,k)
g[i][j]+=(g[k][j-1]+g[i-k][j-1]-g[k][j-1]*g[i-k][j-1])/(i-1);
}
}
db ans=0;
rep(1,n,i)ans+=g[n][i];
printf("%.6lf",ans);
}
return 0;
}