有一种常用的数据生成树的方法是对于 $i\in[2,N]$，随机 ${fa}_i=rand[1,i-1]$。这样生成的树期望高度是 $logN$ 级别的，但这个期望的具体值能不能计算呢，复杂度是多少。

一个例子：三个点按照规则可以生成两棵合法的树（2的父亲只能是1，3有两种可能），高度分别为2和3（假如根的高度是1），那么 $N=3$ 时期望高度就是 $\frac{5}{2}$。

如果上面这个问题可以解决，那么能否求出上面那个规则生成的树以每一个结点为根的时候的期望高度呢？举个例子，还是三个点，综合两棵合法的树可以得到期望值分别是 $\frac{5}{2},\frac{5}{2},3$，因为发现无论如何3为根是树的高度都是3。

希望有大佬来解答我的疑问。