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

---

题外话：

还是那句话，正难则反。

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