概率期望训练之五

https://www.luogu.org/problem/CF696B

又是一种期望模型

分析：

考虑节点u，它的兄弟在它的前面的概率都为0.5

由于期望的线性性

E(在每个兄弟的后面)=E(V1在它前面)+E(V2在它前面)+....+E(Vk在它前面)+0.5，其中k为除它以外的兄弟数

E(u)=0.5×sz[V1]+0.5×sz[V2]+...+0.5×sz[Vk]+0.5

E(u)=0.5×(sz[fa[u]]-sz[u]+1)

预处理出sz就可

code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 100005
using namespace std;

inline int rd(){
    int x=0,f=1;char c=' ';
    while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();
    while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();
    return x*f;
}

int n,siz[N],cnt,to[N],nxt[N],head[N];
double f[N];

inline void add(int x,int y){
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}

void dfs1(int u,int fa){
    siz[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i]; if(v==fa)continue;
        dfs1(v,u); siz[u]+=siz[v];
    }
}

void dfs2(int u,int fa){
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i]; if(v==fa)continue;
        f[v]=f[u]+0.5*(siz[u]-siz[v]+1);
        dfs2(v,u);
    }
}

int main(){
    n=rd();
    for(int i=2;i<=n;i++){
        int fa=rd(); add(fa,i);
    }
    f[1]=1;
    dfs1(1,0); dfs2(1,0);
    for(int i=1;i<=n;i++) printf("%.1lf ",f[i]);
    return 0;
}

概率期望训练之五

原文：https://www.cnblogs.com/wzxbeliever/p/11756017.html