这里再供一个我认为更为正确的翻译。
剪贴板连接
题目描述
给定一棵有根树,结点编号从 1 到 n。根结点为 1 号结点。
对于每一次操作,等概率的选择一个尚未被删去的结点并将它及其子树全部删去。当所有结点被删除之后,游戏结束;也就是说,删除 1 号结点后游戏即结束。
要求求出删除所有结点的期望操作次数。
输入格式
第一行,一个正整数 n 表示结点数量。
接下来 n−1 行每行两个数,表示树上的一条连接 ai 与 bi 的边 (ai,bi)
保证给定的数据是一棵树。
输出格式
输出一个实数,表示期望操作次数。答案误差在 10−6 之内则认为正确。
样例解释
在第一个样例中,有两种情况:
一种是直接删除根(即 1 号结点),另一种是先删去 2 号结点,再删除 1 号结点。
操作次数的期望是 1×21+2×21=1.5。
在第二个样例中,情况更为复杂。其中有两种情况会将问题转化成第一个样例,而剩下的一种情况会一次全部删除。
操作次数的期望是 1×31+(1+1.5)×32=31+35=2。