题目链接 ： CF280C Game on Tree
题意 ： 给定一棵n个节点的树T 根为一（我咕的翻译漏掉了。。。）
每次随机选择一个未被删除的点 并将它的子树删除
求删整棵树的期望步数
n ∈ [1, 1e5]
裸期望问题
考虑贡献
如果要避开一个点对其他点的影响关系【蒟蒻觉得这是期望问题最重要的点
一个点的贡献就只看它自己 不看它的子树
这时每个点如果对结果有贡献 那么就是选中了它 它还没被删
这个的概率就是它上面的节点（父亲、各辈祖宗） 都没被删
由此得
E = Σa P(a被选择时没被删) * 1 = Σa （1 / dep[a]）
附上代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + ;
int n, k;
int dep[N];
struct Edge{
int v, next;
}edge[N << ];
int head[N], esize;
double e; inline void addedge(int x, int y){
edge[++esize] = (Edge){y, head[x]};
head[x] = esize;
} void calc(int x, int fa){
dep[x] = dep[fa] + ;
for(int i = head[x], vv; i != -; i = edge[i].next){
vv = edge[i].v;
if(vv == fa) continue;
calc(vv, x);
}
} int main(){
scanf("%d", &n);
for(int i = ; i <= n; i++) head[i] = -;
for(int i = , x, y; i < n; i++){
scanf("%d%d", &x, &y);
addedge(x, y); addedge(y, x);
}
dep[] = ;
calc(, );
for(int i = ; i <= n; i++)
e += (1.0 / (1.0 * dep[i]));
printf("%lf", e);
return ;
}