首先第一问是原神，设 $f_i$ 表示 $i$ 个叶子的期望深度，那么 $f_n=\dfrac{(n-1)f_{n-1}+2*(f_{n-1}+1)}{n}=f_{n-1}+\frac{2}{n}$。

然后考虑第二问，我们本质上需要求的是 $\sum\limits_{i=1}\limits^{n}iP(i)$，其中 $P(i)$ 表示叶子最大深度等于 $i$ 的概率，然后根据经典结论这个等于 $\sum\limits_{i=1}\limits^{n}Q(i)$，$Q(i)$ 表示 $P(i)$ 的后缀和，也就是最大深度大于等于 $i$ 的概率。

概率我算不来，所以转成方案数，设 $f_{i,j}$ 表示 $i$ 个叶子，最大深度大于等于 $j$ 的方案数，那么 $f_{i,j}=\sum\limits_{k=1}\limits^{i-1}\binom{i-2}{k-1}\{(k-1)!(i-k-1)!-[(k-1)!-f_{k,j-1}][(i-k-1)!-f_{i-k,j-1}]\}$，然后 $\binom{i-2}{k-1}$ 是因为要组成 $i$ 个叶子需要 $i-1$ 次操作，除去根用掉的一次还要 $i-2$ 次，这 $i-2$ 次要先分给两个子树，$k$ 是在枚举左儿子的叶子个数，然后后面那坨东西就是总方案数减去两边都小于 $j$ 的。

所以总时间复杂度是 $O(n^3)$，然后 $f_{i,j}$ 是卷积上 FFT 可以做到 $O(n^2\log n)$。