题解 CF280C 【Game on Tree】
tommymio
·
·
题解
引入《算法导论》中的指示器随机变量确实非常好用，几乎可以以模板化的方式解决一类问题。
约定
$E[X]$ 为 $X$ 的期望值。
$I\{X\}$ 为事件 $X$ 的指示器随机变量。当事件 $X$ 发生时，$I\{X\}$ 的值为 $1$，当事件 $X$ 不发生时，值为 $0$。
### 分析
设 $X_i$ 为事件 $T$ 的指示器随机变量，其中事件 $T$ 为节点 $i$ 被选中。那么总共选出的节点数为 $X=\sum\limits_{i=1}^n X_i$。对等式两边同时期望，得到 $E[X]=E\left[\sum\limits_{i=1}^n X_i\right]$。根据期望的线性性质 $E[Y+Z]=E[Y]+E[Z]$，可以得到 $E[X]=\sum\limits_{i=1}^nE[X_i]$。
又因为 $E[X_i]$ 的值非 $0$ 即 $1$，根据期望的定义式，可以得到 $\forall i,E[X_i]=Pr\{T\}\times 1+Pr\{\bar{T}\}\times 0=Pr\{T\}$，即 $E[X_i]$ 的值为节点 $i$ 被选中的概率。
本题中，只要解决了节点 $i$ 被选中的概率，问题便迎刃而解。观察题目可以发现，如果节点 $i$ 的祖先被选中了，节点 $i$ 便不可能再被选中，也就是说，节点 $i$ 一定要先于它的祖先被选中。那么，节点 $i$ 被选中的概率就为 $\frac{1}{dep_i}$，总共期望选出的节点数即为 $\sum\limits_{i=1}^n\frac{1}{dep_i}$。
### 总结
这类题目，使用指示器随机变量求解就是三部曲：
- 设事件 $T$ 的指示器随机变量。
- 利用指示器随机变量和期望的线性性质分化问题。
- 求解事件 $T$ 发生的概率。
使用指示器随机变量可以让我们迅速看清问题的本质。
关于指示器随机变量的更多应用和介绍可以看另一篇题解（[戳这里](https://www.luogu.com.cn/blog/infinity-dimension/solution-uva12004)），有时间的话我可能会整理出指示器随机变量的各种应用（
### 代码
```cpp
#include<cstdio>
double ans=0.00;
int cnt=0;
int h[100005],to[200005],ver[200005];
inline int read() {
register int x=0,f=1;register char s=getchar();
while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
return x*f;
}
inline void add(int x,int y) {to[++cnt]=y;ver[cnt]=h[x];h[x]=cnt;}
inline void dfs(int x,int dep,int fa) {
ans+=1.00/dep;
for(register int i=h[x],y;i;i=ver[i]) {if((y=to[i])==fa) continue; dfs(y,dep+1,x);}
}
int main() {
int n=read();
for(register int i=1,x,y;i<n;++i) {x=read();y=read();add(x,y);add(y,x);}
dfs(1,1,-1); printf("%.6lf\n",ans);
return 0;
}
```