Codeforces 839C(期望+DFS)

Codeforces 839C
dfs维护每个点到达的概率$p_i$和到根节点距离$d_i$,然后枚举叶子节点累加$p_i \times d_i$即可。

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 10;
int n, dep[MAXN], yz[MAXN];
db p[MAXN];
vector<int> G[MAXN];
void dfs(int u, int pa) {
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != pa) {
dep[v] = dep[u] + 1, p[v] *= p[u] * (db)1.0 / (db)((int)G[u].size() - 1);
dfs(v, u);
}
}
if ((int)G[u].size() == 1) yz[u] = true;
}
void clean() {
for (int i = 1; i <= n; i++) yz[i] = false, dep[i] = 0, p[i] = 1.0;
}
void solve() {
clean();
for (int u, v, i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
G[1].push_back(0);
dfs(1, 0);
db ans = 0;
for (int i = 1; i <= n; i++)
if (yz[i]) ans += (db)dep[i] * p[i];
printf("%.9f\n", ans);
}
int main() {
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------