题意：中文题，按照题目要求的二叉树生成方式，问（1）叶平均深度 （2）树平均深度
解法：这道题看完题之后完全没头绪，无奈看题解果然不是我能想到的qwq。题解参考https://blog.csdn.net/Maxwei_wzj/article/details/82262755这位大佬的，这里讲下我的理解：
首先是第一问：第一问会简单一些，设f[i]代表叶节点为i的树的叶平均深度，那么因为是平均那么 i*f[i] 就是叶子总深度啦。在叶子深度x下拓展得到的新贡献是 2(x+1)-x=x+2 。那么就有 i*f[i]=(i-1)*f[i-1]+x+2 。这里的x是什么呢？x是叶子深度当然要是期望情况下的深度，那不就恰好是f[i]吗！！
那么得到 i*f[i]=(i-1)*f[i-1]+f[i-1]+2 化简得到 f[i]=f[i-1]+2/n 。第一问解决。
第二问思维难度会更大一些：令g[i][j]代表叶子数为i的树深度大于等于j的概率。
那么会得到状态转移方程： g[i][j]=1/(i-1) * sigma(g[k][j-1]+g[i-k][j-1]) (k=1~i-1);
解释一下就是把i个叶子分给左右子树（当然左右都至少有一个叶子所以才是i-1种情况），然后加上根节点的深度要求左边的概率就是g[k][j-1]，右边的概率就是g[i-k][j-1]。但是这样会加多了（因为g[i][j]是没有区分左右的所以直接加，左右都满足条件的会加了两次），所以要减去相乘的结果。
至于这个方程最重要的一点是为什么结果能除以i-1？这个结论需要证明，建议看上面大佬或者洛谷大佬的题解证明过程。结论就是：
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100+10; 4 int q,n; 5 6 double dp1[N]; //dp1[i]代表：i个结点的平均深度期望为dp1[i] 7 void solve1() { 8 dp1[1]=0; 9 for (int i=2;i<=n;i++) dp1[i]=dp1[i-1]+2/(double)i; 10 printf("%.6lf\n",dp1[n]); 11 } 12 13 double dp2[N][N]; //dp2[i][j]代表：i个结点树深度大于等于j的概率 14 void solve2() { 15 dp2[1][0]=1; 16 for (int i=2;i<=n;i++) { 17 dp2[i][0]=1; 18 for (int j=1;j<=n;j++) { 19 for (int k=1;k<i;k++) 20 dp2[i][j]+=dp2[k][j-1]+dp2[i-k][j-1]-dp2[k][j-1]*dp2[i-k][j-1]; 21 dp2[i][j]/=(double)(i-1); 22 } 23 } 24 double ans=0; 25 for (int i=1;i<n;i++) ans+=(dp2[n][i]-dp2[n][i+1])*i; 26 printf("%.6lf\n",ans); 27 } 28 29 int main() 30 { 31 cin>>q>>n; 32 if (q==1) solve1(); 33 else solve2(); 34 return 0; 35 }