期望多少次操作,我们可以看做是染黑了多少节点
那么,我们可以用期望的线性性质,求出每个节点被染黑的概率之和(权值为$1$)
一个节点$u$被染黑仅跟祖先有关
我们把$u$到祖先的链抽出来
只要选取链上任意一点,那么我们对节点$u$的染黑的概率就讨论完了
发现链以外的点对这条链的影响都是相同的
也就是说,选取这条链上的一个点的概率都是相同的
因此,选取点$u$的概率就是这条链的节点数的倒数,也就是$\frac{1}{dep_u}$
最后的结果就是对每个点进行求和
$\sum\limits_{1 \leqslant i \leqslant n} \frac{1}{dep_i}$
复杂度$O(n)$
这道题对期望的应用还是挺妙的,并且可扩展性十分的强,挺适合拿来改题的
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
namespace remoon {
#define de double
#define ri register int
#define tpr template <typename ra>
#define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++)
#define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --)
#define gc getchar
inline int read() {
int p = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
}
using namespace std;
using namespace remoon;#define sid 300050int n, cnp;
int cap[sid], nxt[sid], node[sid], dep[sid];
de ans;inline void addedge(int u, int v) {
nxt[++ cnp] = cap[u]; cap[u] = cnp; node[cnp] = v;
}#define cur node[i]
inline void dfs(int o, int fa) {
dep[o] = dep[fa] + ;
ans += / (de)dep[o];
for(int i = cap[o]; i; i = nxt[i])
if(cur != fa) dfs(cur, o);
}int main() {
n = read();
rep(i, , n) {
int u = read(), v = read();
addedge(u, v); addedge(v, u);
}
dfs(, );
printf("%lf\n", ans);
return ;
}