CF280C game on tree（数学期望）

121 阅读 0 评论 80 点赞

我是靠谱客的博主无奈黑夜，这篇文章主要介绍CF280C game on tree（数学期望），现在分享给大家，希望可以做个参考。

题意：

题目描述

给出一棵树，每次随机等概率选择一未染黑的点，将它及其子树染黑。问期望多少次操作可以将树全部染黑。

输入格式

第一行为一个整数 n，描述这棵树有 n 个节点。

接下来 n-1 行，每行两个整数 ai和 bi ，描述这个树的其中一条边的起点和终点的编号分别为 ai 和 bi 。

输出格式

输出一个实数，为描述的期望。

你的答案与标准答案若相差不超过 10^{-6}

，则你的答案就是正确的。

将树全部染黑，可以等价于把根结点染黑，所以只需求选到根结点操作数的期望。

因为选到了一个点，它的所有子结点就不会被选到了，所以每个点一定在它的祖先被选到之前被选到。

所以选每个点的概率为 1/该点的祖先数（包括自己），即1/depth[i]，选该点的期望也是1/dep[i]。

所以只需要将每个点选到的期望相加即可。

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,x,y,head[100010],depth[100010],cnt;
double ans;
struct Tree
{
	int next;
	to;
}e[100010];
inline void insert(int x,int y)
{
	e[++cnt].next=head[x];
	e[cnt].to=y;
	head[x]=cnt;
}
void dfs(int u,int fa){
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa) continue;
        depth[v]=depth[u]+1;
        dfs(v,u);
    }
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        insert(x,y);insert(y,x);
    }
    depth[1]=1;dfs(1,-1);
    for (int i=1;i<=n;i++) ans=ans+1.0*1/depth[i];
    printf("%.20lfn",ans);
    return 0;
}