题目描述

有一棵以 $1$ 为根的有根树，包含 $n$ 个节点。游戏过程如下：

• 每一步，从当前剩余的节点中均匀随机选择一个节点 $v$。
• 删除以 $v$ 为根的整个子树（包括 $v$ 本身）。
• 游戏在删除根节点 $1$ 后结束（此时树为空）。

求游戏步数的期望值。

解法分析

关键转化

考虑任意一个节点 $v$。它会在什么情况下作为一次“被选中的节点”而贡献一步？

• 如果 $v$ 的某个祖先 $u$（$u \neq v$）在 $v$ 之前被选中，那么 $v$ 将在 $u$ 被选中的那一步中被连带删除，不会单独被选中。
• 只有当从根到 $v$ 的路径上的所有节点中，$v$ 是第一个被选中的节点时，$v$ 才会成为一次选中的节点，贡献 $1$ 步。

因此，节点 $v$ 对总步数的贡献是一个指示随机变量 $I_v$，$I_v = 1$ 当且仅当 $v$ 是根到 $v$ 路径上第一个被选中的节点。

概率计算

设 $d_v$ 为节点 $v$ 的深度（根深度为 $1$）。根到 $v$ 的路径上有 $d_v$ 个节点。
由于每一步都是均匀随机地从剩余节点中选取，且删除操作不会改变路径上节点之间的相对顺序（它们互为祖先‑后代关系），可以证明：这 $d_v$ 个节点在游戏中被选中的顺序是均匀随机的，所有 $d_v!$ 种排列等可能。
因此，$v$ 成为第一个被选中的概率为 $\dfrac{1}{d_v}$。

期望步数

由期望的线性性质：

$$E = \sum_{v=1}^{n} \Pr(\text{$v$ 被单独选中}) = \sum_{v=1}^{n} \frac{1}{d_v}. $$

算法步骤

1. 读入 $n$ 和 $n-1$ 条边，建树。
2. 以 $1$ 为根进行 DFS 或 BFS，计算每个节点的深度 $d_v$（根深度为 $1$）。
3. 累加 $\sum_{v=1}^{n} \frac{1}{d_v}$，输出结果。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

标程

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<int> depth(n + 1, 0);
    function<void(int, int)> dfs = [&](int u, int p) {
        depth[u] = depth[p] + 1;   // 根 depth[1] = 1
        for (int v : g[u]) {
            if (v != p) dfs(v, u);
        }
    };
    dfs(1, 0);

    double ans = 0.0;
    for (int i = 1; i <= n; ++i) {
        ans += 1.0 / depth[i];
    }
    cout << fixed << setprecision(15) << ans << '\n';
    return 0;
}