[题目链接]
http://codeforces.com/contest/839/problem/C
[算法]
概率DP
时间复杂度 : O(N)
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010int 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 ;}