题意是给出一棵有根树,每次等概率删除一个点以及以其为根的子树,问删完整棵树的期望步数。
暴力枚举方案显然不可,考虑期望的线性性质,将问题转化为删除每个点的期望步数再求和。一个点消失要么是选中了这个点的某个祖先(对这个点的期望没有贡献),要么是直接删除这个点。换句话说,一条链上每个点首先被删除的概率是相等的。设这个点的深度为dep,那么删除这个点的概率为\(\frac{1}{dep}\),步数为1,对期望的贡献为\(\frac{1}{dep}\times 1\)。dfs一遍更新答案即可。
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, head[N], ver[2 * N], Next[2 * N], tot = 0;
void add(int x, int y) {
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
double ans = 0;
void dfs(int x, int pre, int dep) {
ans += 1.0 / dep;
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(y == pre) continue;
dfs(y, x, dep + 1);
}
}
int main() {
cin >> n;
for(int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1, 0, 1);
cout << fixed << setprecision(8) << ans << endl;
return 0;
}
标签:head,期望,int,Tree,Codeforces,tot,dep,dfs,Round
From: https://www.cnblogs.com/lipoicyclic/p/16882391.html