题目链接：Codeforces 280C

Momiji 有一棵包含 $n$ 个节点的有根树。节点从 $1$ 到 $n$ 编号，其中根节点的编号为 $1​$。Momiji 打算在这棵树上玩一个游戏。

整个游戏包含很多步。每一步，Momiji 选择一个存在的节点，然后把这个节点作为根的子树删除，选择的节点本身也被删除。当这棵树为空时，游戏结束。换言之，当节点 $1$ 被删除后游戏结束。

你需要求出游戏结束的期望步数。

数据范围：$1 \le n \le 10 ^ 5$。

Solution

由于每个点都会被删除，我们对每个点计算贡献。考虑第 $i$ 个点是怎么被删除的：

• 直接删除 $i$ 这个节点。
• 删除 $i$ 的父亲。
• 删除 $i$ 的父亲的父亲。
• 删除 $i$ 的父亲的父亲的父亲。
• ……
• 删除根节点。

这一共深度个方法，对答案有贡献的方法只有直接删除其本身！那么我们设第 $i$ 个点的深度为 $\text{dep}_i$，那么答案为：

$$ \sum_{i = 1} ^ n \frac{1}{\text{dep}_i} $$

时间复杂度：$\mathcal O(n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e5 + 5, M = 2e5 + 5;

int n, tot, lnk[N], ter[M], nxt[M], dep[N];

void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        dfs(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs(1, 0);
    double ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += 1.0 / dep[i];
    }
    printf("%.10lf\n", ans);
    return 0;
}