[题目链接]

http://codeforces.com/contest/839/problem/C

[算法]

概率DP

时间复杂度 : O(N)

[代码]

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010 int tot , n;
int head[MAXN];
bool visited[MAXN];
double f[MAXN]; struct edge
{
int to , nxt;
} e[MAXN << ]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
inline void addedge(int u,int v)
{
tot++;
e[tot] = (edge){v,head[u]};
head[u] = tot;
}
inline double dp(int u,int fa)
{
int cnt = ;
if (visited[u]) return f[u];
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa) continue;
cnt++;
}
if (cnt == )
{
visited[u] = true;
return f[u] = ;
}
f[u] = ;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa) continue;
f[u] += 1.0 / cnt * dp(v,u);
}
visited[u] = true;
return f[u];
} int main()
{ read(n);
for (int i = ; i < n; i++)
{
int u , v;
read(u); read(v);
addedge(u,v);
addedge(v,u);
}
memset(visited,false,sizeof(visited));
printf("%.10lf\n",dp(,)); return ; }

最新文章

  1. jQuery学习之路(7)- 用原生JavaScript实现jQuery的某些简单功能
  2. 集合覆盖 顶点覆盖: set cover和vertex cover
  3. 关于ssh_copy_id脚本解析
  4. Android 视频播放器进度的处理
  5. Flash 二进制传图片到后台Java服务器接收
  6. ubuntu安装cacti错误
  7. ASP.NET 图片上传工具类 upload image简单好用功能齐全
  8. 【SGU 104】Little shop of flowers
  9. BZOJ-1013 球形空间产生器sphere 高斯消元+数论推公式
  10. annotation(@Retention@Target)详解
  11. c++标准库中几个常见的数据结构的区别和应用规则
  12. 李洪强经典iOS面试题11
  13. Java虚拟机的内存组成以及堆内存介绍
  14. 如何让图片在div里面剧中显示
  15. js动弹特效
  16. List&lt;String&gt; 和 ArrayList&lt;String&gt;的区别
  17. 关于Springboot整合mybatis启动的问题
  18. C++之异常捕获和处理
  19. dagger2的初次使用
  20. 防火墙禁ping:虚拟机ping不通主机,但主机可以ping虚拟机

热门文章

  1. isinstance()和issubclass()
  2. uva 662
  3. DLL混淆
  4. Deepin-安装(读写文件)权限
  5. fixedBox固定div漂浮代码 支持ie6以上大部分浏览器
  6. android findVIewById()在线生成工具
  7. Python 离线等价类
  8. GCC 编译详解 (转)
  9. 【iOS系列】-textView的非常规使用
  10. Activity动态添加Fragment时遇到的问题