题意
给定一棵树，每次随机选一个点永久删除它及它的所有子树。输出一个实数表示期望被删空的次数。
$n = 10^5$，$0.5$ 秒
题解
结论：$ans = \sum\limits_{i = 1}^n1/dep_i$
如果我们要删除点 $i$，那么要么直接删除 $i$，要么删除 $i$ 的一个祖先。只有直接删除 $i$ 时，我们才将这笔账记在 $i$ 头上。因此点 $i$ 只有 $1/dep_i$ 的概率产生 $1$ 的贡献（即产生 $1/dep_i$ 的贡献）。于是最终期望就是 $\sum\limits_{i = 1}^n1/dep_i$
代码
// :/
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n = bin;
vector<vector<tp>> e(n);
while (--n) {
tp u, v; bin >> u >> v;
--u; --v;
e[u].push_back(v);
e[v].push_back(u);
}
auto dfs = [&](auto $, tp f, tp x, tp dep) -> double {
double ret = 1. / dep;
for (auto& i : e[x]) {
if (i != f) ret += $($, x, i, dep + 1);
}
return ret;
};
bin << CALL(dfs, 0, 0, 1) << '\n';
}
void MIST() {
}
// :\ */