CF280C Game on Tree 题解

题目链接：Game on Tree

题意：

给定一棵有根树，结点编号从 \(1\) 到 \(n\)。根结点为 \(1\) 号结点。

对于每一次操作，等概率的选择一个尚未被删去的结点并将它及其子树全部删去。当所有结点被删除之后，游戏结束；也就是说，删除 \(1\) 号结点后游戏即结束。

要求求出删除所有结点的期望操作次数。

输入格式

第一行，一个正整数 \(n(1 \le n \le 10^5)\) 表示结点数量。

接下来 \(n-1\) 行每行两个数，表示树上的一条连接 \(a_i\) 与 \(b_i\) 的边 \((a_i,b_i)\)

保证给定的数据是一棵树。

输出格式

输出一个实数，表示期望操作次数。答案误差在 \(10^{-6}\) 之内则认为正确。

显然，当且仅当一个节点比它的所有的祖先都要优先删除时，它会对操作次数产生 \(1\) 的贡献

于是我们可以单独考虑每个点对答案的期望贡献。

设 \(f_i\) 为点 \(i\) 直接选中时对答案的期望贡献，则 \[ f_i = \frac{1}{p} \times 0 + p \times 1 \] 其中 \(p\) 为 \(i\) 在它祖先之前的概率，显然 \(p = \frac{1}{\mathtt{dep}(u)}\) ，其中 \(\mathtt{dep}\) 表示深度，\(\mathtt{dep}(1)=1\) 。

那么答案就是 \(\sum_i f_i = \sum_i \frac{1}{\mathtt{dep}(i)}\) 。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

double ans; int dep[N];
vector<int> vec[N];
void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1; ans += 1.0 / dep[u];
    for(int v : vec[u]) if(v != fa) { dfs(v, u); }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1, u, v; i < n; i++) {
        cin >> u >> v; vec[u].push_back(v); vec[v].push_back(u);
    }
    dfs(1, 0); cout << fixed << setprecision(8) <<  ans << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/b9zdkpf1

---

题外话：

还是那句话，正难则反。

本题不是很好找到从子树转移的方程，因此可以考虑每个节点为怎么对它的祖先产生贡献。