数学期望

Codeforces 839C Journeyhttp://codeforces.com/problemset/problem/839/C

不能求总和除以个数来做。

假设无向图1-2，2-3，1-4，3-4
Ei(i=1,2,3,4) 表示从i号节点走到4号节点的数学期望值

E1=(1/3)∗E1+(1/3)∗E2+(1/3)∗E3+1（参考http://blog.csdn.net/helloworld10086/article/details/48714159）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<vector>
 7 #define lson l, m, rt<<1
 8 #define rson m+1, r, rt<<1|1
 9 #define IO ios::sync_with_stdio(false);cin.tie(0);
10 #define INF 1e18
11 typedef long long ll;
12 using namespace std;
13 ll n, vis[100010], dist=0, ans=0;
14 vector<int> vec[100010];
15 double dfs(int cur)
16 {
17     int flag=0, cnt=0;
18     double tmp=0;
19     for(int i = 0; i < vec[cur].size(); i++){
20         if(!vis[vec[cur][i]]){
21             flag=1;
22             vis[vec[cur][i]] = 1;
23             cnt++;
24             tmp += dfs(vec[cur][i]);
25         }
26     }
27     if(!flag){
28         return 0.0;
29     }
30     else return 1.0+tmp/cnt;
31 }
32 int main()
33 {
34     int x, y;
35     cin >> n;
36     for(int i = 0; i < n-1; i++){
37         cin >> x >> y;
38         vec[x].push_back(y);
39         vec[y].push_back(x);
40     }
41     vis[1] = 1;
42     printf("%.6lf
", dfs(1));
43     return 0;
44 }