随机选父亲法
随机选父亲法代码如下：
void RandomFatherGenerator(int n, Graph &g){
std::mt19937 rnd(time(nullptr));
for(int i=2;i<=n;i++){
g.addUndirectedEdge(rnd%(i-1)+1, i);
}
}
上述代码会生成一个以 \(1\) 为根的树。
每个点的期望深度
用随机选父亲法构造一个 \(n\) 个点的树，求每个点的期望深度。
我们都知道随机选父亲法生成的树深度期望 \(O(\log n)\)。但如果我们需要求精确值呢？
一个朴素的 ytxy 的 \(O(n^3)\) 做法：设 \(f(i,j)\) 表示第 \(i\) 个点深度为 \(j\) 的概率。
容易得到：
\[f(i,j) = \frac{1}{i-1}\sum_{k=1}^{i-1} f(k,j-1)
\]
最后第 \(i\) 个点答案：
\[\sum_{k=1}^{i} f(i,k)k
\]
一个朴素的 \(O(n^2)\) 做法。我们发现 \(f(,j)\) 中的 \(j\) 完全就是一个多余的东西。因此我们无须这个状态。
设 \(f(i)\) 为第 \(i\) 个节点的深度期望。
\[f(i)=1+\frac{1}{i-1}\sum_{k=1}^{i-1} f(k)
\]
用前缀和即可优化到 \(O(n)\)。
给个 python 代码吧：
pre,f,n = 1,1,10
for i in range(1, n + 1):
print(f)
f = 1 + (1 / (i)) * pre
pre += f