比较死板的一个 trick。
首先我们设 \(f_{i, j}\) 为以 \(i\) 为根的子树深度为 \(j\) 的方案数，由于是往底下接一个点，容易做到 \(O(n^2)\) 的复杂度。
但是你想想，假设我们目前想求深度为 \(d\) 的概率为多少，考虑最坏情况下到 \(d\) 的路径一共有 \(n\) 条，那么其深度为 \(d\) 的概率大概我们可以估出：
\[1 - (1 - \frac{1}{2^d})^n
\]
当 \(d\) 越大的时候，这个东西是越小的，由于保留 \(6\) 位误差，所以当 \(d = 60\) 时，就不对答案产生影响了。
所以我们 DP 第二维只保留 \(60\) 即可，复杂度大概是 \(O(60n)\)。