题意是给出一棵有根树，每次等概率删除一个点以及以其为根的子树，问删完整棵树的期望步数。
暴力枚举方案显然不可，考虑期望的线性性质，将问题转化为删除每个点的期望步数再求和。一个点消失要么是选中了这个点的某个祖先（对这个点的期望没有贡献），要么是直接删除这个点。换句话说，一条链上每个点首先被删除的概率是相等的。设这个点的深度为dep，那么删除这个点的概率为\(\frac{1}{dep}\)，步数为1，对期望的贡献为\(\frac{1}{dep}\times 1\)。dfs一遍更新答案即可。
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, head[N], ver[2 * N], Next[2 * N], tot = 0;
void add(int x, int y) {
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
double ans = 0;
void dfs(int x, int pre, int dep) {
ans += 1.0 / dep;
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(y == pre) continue;
dfs(y, x, dep + 1);
}
}
int main() {
cin >> n;
for(int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1, 0, 1);
cout << fixed << setprecision(8) << ans << endl;
return 0;
}