给定n个数,求i的位置的期望

那么反向考虑,j!=i排在i前面的概率是0.5,那么对i的位置的期望贡献就是1*0.5

这题就是拓展应用一下

#include<bits/stdc++.h>
using namespace std; const int maxn = ;
const double esp = 1e-; vector<int>G[maxn];
int n,size[maxn];
double E[maxn]; void dfs1(int u,int pre){
size[u]=;
for(int i=;i<G[u].size();i++){
int v=G[u][i];
if(v==pre)continue;
dfs1(v,u);
size[u]+=size[v];
}
} void dfs2(int u,int pre){
if(u==)E[u]=1.0;
for(int i=;i<G[u].size();i++){
int v=G[u][i];
if(v==pre)continue;
E[v]=1.0*(size[u]-size[v]-)/+E[u]+;
dfs2(v,u);
}
} int main(){
cin>>n;
for(int i=;i<=n;i++){
int fa;
cin>>fa;
G[fa].push_back(i);
G[i].push_back(fa);
}
dfs1(,);
dfs2(,);
for(int i=;i<=n;i++)
cout<<E[i]<<" ";
}

最新文章

  1. 基于HTML5实现3D监控应用流动效果
  2. Excel—利用散点图计算相关系数
  3. 从零开始学 Java - Spring MVC 统一异常处理
  4. java中Thread的 interrupt异常处理
  5. sql数据库常用语句总结
  6. (十)stm32中FSMC的使用(用于LCD)
  7. 【FreeBuf视频】《安全大咖说》专访知道创宇CTO杨冀龙(watercloud)
  8. 使用SQLServer Audit来监控触发器的启用、禁用情况
  9. OpenCV1.0在VC ++6.0下的配置
  10. flume 搭建
  11. [福大软工] W班 第2次成绩排行榜
  12. beta冲刺4
  13. Android系统对话框
  14. 关于python深浅拷贝的个人浅见
  15. 使用Spring表达式语言进行装备--SpEL
  16. Oracle学习笔记之触发器
  17. Hdoj 1213.How Many Tables 题解
  18. 获取当前div以外所有部分
  19. iOS UI调试神器,插件injection for Xcode使用方法
  20. Linux命令(八)过滤文本 grep

热门文章

  1. 一起感受HTML5和CSS3
  2. MySQL 小调研
  3. RedHat版本Linux安装chrome-stable配合chromeDriver进行自动化测试环境准备
  4. 七种数据库中Select Top的使用方法 (只显示数据库的几条记录)
  5. js条件语句,用if...else if....else方程ax2+bx+c=0一元二次方程。求根
  6. thinkphp url重写
  7. 2019hdu第二场
  8. 检测API函数的InlineHook
  9. 转-Windows下anaconda简单使用教程
  10. flutter layout-child