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;
- }
来源: http://www.bubuko.com/infodetail-3262791.html